obj-arch-table asked how many bytes an instruction is and would not answer. The ModRM concept said mod and rm decide the trailing bytes. The SIB concept found a case where that is not quite enough. This concept closes it: one formula, and the reason a formula beats a table.
$ ./build_samples.sh 2>&1 | sed -n '/I8/,$p' length = prefixes + opcode + modrm + sib + displacement + immediate bytes prefixes+op modrm sib disp imm sum measured 8b 00 8b 1 - - - 2 2 ok 48 8b 00 48 8b 1 - - - 3 3 ok 8b 04 24 8b 1 24 - - 3 3 ok 8b 40 11 8b 1 - 1 - 3 3 ok 8b 80 11 22 33 44 8b 1 - 4 - 6 6 ok 8b 05 44 33 22 11 8b 1 - 4 - 6 6 ok 8b 84 24 11 22 33 44 8b 1 24 4 - 7 7 ok 83 c0 01 83 c0 - - 1 3 3 ok b8 11 22 33 44 b8 - - - 4 5 5 ok 48 b8 11 22 33 44 55 66 77 88 48 b8 - - - 8 10 10 ok 66 b8 11 22 66 b8 - - - 2 4 4 ok f6 c0 01 f6 c0 - - 1 3 3 ok f6 d0 f6 d0 - - - 2 2 ok 66 2e 0f 1f 84 00 00 00 00 00 66 2e 0f 1f 84 00 4 - 10 10 ok every row matches: True
Fourteen rows, every one matching, and the formula is a single line. Length is not a property of the opcode. It is a sum of six independent contributions, and each contribution is decided by a different part of the encoding.
The longest row is the one to read twice. 66 2E 0F 1F 84 00 00 00 00 00 is ten bytes: two legacy prefixes, the two-byte escape, a ModRM, a SIB and a disp32. It is the canonical multi-byte NOP that compilers emit for alignment padding, which means real binaries are full of them and any decoder has to get this exact shape right.
And the shortest is one byte: ret is C3 and nothing else. So the same instruction format spans 1 to 15 bytes, and the span is a design choice rather than an accident.
The formula, and then the two places where a naive implementation of it is wrong:
Rule 1 is the one that bit this course’s own decoder first, and the way it presented is worth describing because it is a shape of bug the collection has now seen four times. The decoder read the disp32 and then the immediate, and added the immediate twice after an edit — so every instruction with an immediate overran by its own width. It did not crash. It produced plausible-looking output for the first few instructions and then nonsense, which is exactly the failure mode a boundary check exists to catch.
And the semantic point behind rule 1 is real, not just an encoding curiosity. A sign-extended 32-bit immediate is a deliberate design choice: it makes the common case — a small positive or negative constant — cost 4 bytes instead of 8, and 4 bytes is the difference between a 3-byte and a 7-byte instruction. The price is that the full 64-bit range needs a sequence, and the price is paid knowingly.
Rule 2 is the more interesting structural point. The ModRM byte is both data and control. In most opcodes its reg field names a register and its rm field is an address; in ten opcodes the reg field selects which of eight operations this is, and in two of those the selection also determines whether an immediate follows. So:
Now the property that makes a length decoder verifiable, and it is the most important idea in this concept.
Instruction boundaries form a chain: start[0] = 0 and start[i+1] = start[i] + len[i]. So if you decode a code section and the last instruction ends exactly at the section size, then every length was right — or they were wrong in a way that cancelled out, which for a chain of this shape means a compensating pair, and the oracle comparison rules that out.
$ ./build_samples.sh 2>&1 | sed -n '/^I7/,/^I8/p' ok corpus .init 27 B 8 instructions chain exact ok corpus .plt 96 B 18 instructions chain exact ok corpus .plt.got 8 B 2 instructions chain exact ok corpus .text 1741 B 440 instructions chain exact ok corpus .fini 13 B 4 instructions chain exact ok mini .text 288 B 72 instructions chain exact ok probe.o .text 56 B 17 instructions chain exact --- 578/578 instruction boundaries agree (100.00%)
578 of 578 boundaries agree with the oracle, and every chain closes exactly. And the “chain exact” column is the load-bearing one, for a reason that is worth spelling out because it is the difference between a strong test and a weak one:
So the count is a necessary condition and a poor one, and the chain is what makes the check strong. This is the same reasoning the object course’s oracle-loop concept used — three independent readers, byte-exact comparison — applied to a different kind of claim. There, three readers agreed on bytes. Here, two readers agree on structure, and the structure has a property that makes agreement hard to fake.
Now the length distribution, because the shape of real code is a fact rather than an intuition:
$ python3 x86dec.py corpus --- 1885 bytes of code, 472 instructions decoded, mean 3.99 bytes
Plus the histogram from the earlier measurement of a smaller specimen: 1 byte 16 times, 2 bytes 28, 3 bytes 25, 4 bytes 27, 5 bytes 8, 6 bytes 5, 7 bytes 20 — 129 instructions, mean 3.60, and a shape that is nothing like a normal distribution. The modes at 2 and 4 bytes are the register forms and the disp8/disp32 forms; the bump at 7 is the multi-byte NOP padding.
Two consequences follow from that histogram, and both are practical. Code density is the reason the encoding is variable-length at all — a fixed 4 bytes would waste about half the space, and on a machine with a 64K memory that was not affordable. And the 15-byte maximum is essentially never reached: no compiler emits it, because a 15-byte instruction is worse than a call. The architectural limit exists for hand-written code and for the padding NOP, and the measured maximum in real code is 10.
Here is the shape of a complete length function, which is worth writing out because it is short, and everything hard about x86 decoding is in the six decisions rather than the arithmetic:
Thirty lines. And notice which lines are hard: not 4 and not 5, but the two tables those lines consult. TAKES_MODRM is 364 entries, and it is the only part of the decoder that can be wrong without the arithmetic noticing. The table is the vulnerability, and that is why the crosscheck audits it exhaustively rather than spot-checking it.
And the audit is where the method paid for itself. 364 entries audited, 0 length disagreements, and it found four errors that every hand-written example had missed:
Every one of those produced a plausible disassembly of a chosen example. None of them could have been found by reading the decoder, because the decoder has no internal contradiction to notice — it has a table, and a table is just data. The only way to find out a table is wrong is to compare it against something independent, across its whole input space.
That is the argument for the whole method of this collection, stated in its most compressed form:
Which is also, not coincidentally, what the image course’s artifact does and what the hardening course’s reader does. Three courses, three artifacts, one discipline: every value checked against a source that did not produce it.
$ cd courses/isa/assets/samples $ ./build_samples.sh 2>&1 | sed -n '/I7/,$p' $ python3 x86dec.py corpus $ python3 crosscheck.py 2>&1 | sed -n '/^I7/,$p'
Then write the length function and test it the hard way:
1. Implement the length function above and check
it against the oracle for every opcode in
the table -- not every instruction, every
OPCODE, in every form:
for each table entry:
build a minimal instruction
assert length(...) == oracle(bs)
(The crosscheck already does this as check I9:
364 entries, 38 skipped as invalid, 0
disagreements. Re-derive it and then BREAK one
entry deliberately -- change 0F F4 to 'hlt' and
watch I9 fail. A checker that has never failed
is not known to work.)
2. Now the property test, which is stronger and
costs less. Decode every code section of
several real binaries and require the chain
to close:
for b in ('corpus','mini','probe.o'):
d, secs = x86dec.code_sections(b)
for n,a,o,sz in secs:
ins,end,bad = x86dec.decode_stream(d[o:o+sz],0,sz)
assert end == sz, (b,n,end,sz)
How many sections pass? (All of them, across
every binary you try, or the decoder is wrong
somewhere you have not looked.) This single
assertion catches more than a thousand
per-instruction comparisons would, because it
is sensitive to compensating errors.
3. Find the distribution yourself and check it
against the oracle's, per length:
objdump -d corpus | awk -F'\t' 'NF>2{gsub(/ /,"",$2);
n=split($2,b," "); print n}' | sort -n | uniq -c
Two independent length histograms for the same
binary. They should match exactly. Then
compute the mean and the mode, and ask what
fraction of instructions are 4 bytes or fewer
-- the answer is the code-density argument in
one number, and it justifies the variable-length
encoding better than any amount of prose.
4. Test the two rules that break naive
implementations, as explicit cases:
# rule 1: REX.W does not widen the immediate
48 b8 <8> 10 bytes
b8 <4> 5 bytes
48 c7 40 20 <4> 8 bytes <- the trap
# rule 2: the reg field decides the immediate
f6 c0 01 3 bytes
f6 d0 2 bytes
0f ba c0 01 4 bytes
0f ba e8 3 bytes
(The 0F BA group is the interesting one: BT/BTS/
BTR/BTC take an imm8 and the other four members
do not, so a decoder needs the group table for
the two-byte map as well. Find every such group
in the decoder's GROUPS dictionary and check
each one's rule.)
5. Finally, the experiment that makes the chain
property vivid. Corrupt ONE length in the
decoder -- add 1 to the disp32 case -- and
measure how many instructions are wrong:
# patch: return 4 instead of the computed
# width for mod=10 rm=000
Then count the instructions that still decode
correctly after the first divergence. (A few,
by coincidence, and then none. Count the few:
that is the number of instructions a
per-instruction spot check would have called
"mostly passing".)
Exercise 5 is the one that makes the concept a reflex, and its result is the most useful number in the course. Corrupt one length rule and a per-instruction check still passes for the handful of instructions before the first error, while the chain check fails immediately and locallyises the bug to one specific opcode class. That is the difference between a test that tells you something is wrong and a test that tells you where, and it is why the crosscheck asserts the chain rather than a count.
Exercise 3 answers the question the whole course has been circling. The mean instruction is under 4 bytes, and most instructions are 4 or fewer — which is the measured justification for a variable-length encoding. A fixed-width 4-byte instruction would be barely larger and enormously simpler to decode, and x86 chose the harder design because a 64K memory made the density worth it. That is the trade, stated as a number rather than an assertion, and it is the same reasoning the SIB concept reached for scaled indexing: one byte of encoding to avoid a sequence of instructions.
This concept closes the loop the collection opened in the object course, and the loop is worth naming precisely because it took seven courses to close. obj-arch-table said a linker needs to know how many bytes an instruction is and where the field starts; the relocations concept measured the per-architecture relocation tables that consume the answer; the PIC concept and the relocations course both needed disp32 without being able to say how it is encoded. That is six concepts of debt and this formula pays it — and the way the chain paid it is the method made visible: each course measured what it could, wrote down what it could not, and the missing piece turned out to be exactly one formula plus one table.
The connection to the default-linker-script concept is about what the formula makes possible. That course found the default script’s section-placement rules and could not say why .plt entries are six bytes and .text entries vary. Six bytes is FF 25 plus a mod=00 rm=101 ModRM plus a disp32 — the RIP-relative indirect jump — and the reason it cannot be shorter is that an indirect jump has no register to put the address in. One formula answers a question a linker script raised two courses ago.
Two connections outward, both about verification rather than mechanism. The image course’s artifact established the discipline of checking every value against a source that did not produce it, and the two-level dependency measured here — ModRM says “more”, SIB says “how much” — is the same shape as the image course’s pointer-versus-size warning: a value whose meaning depends on a field you have not read yet. And The posture reader in the hardening course made the same choice for a different format, where two of the eight features it checks leave no header field at all and must be found by searching the bytes. Both readers exist because the interesting properties are not all in the fields, and a format whose interesting parts are hidden in the encoding is a format you have to decode, not just parse.
One limit, and it is the course’s standing one. Every number here was measured on x86-64 against one reader, and the table covers 364 audited entries out of a much larger ISA. The decoder is not a complete disassembler and the crosscheck does not pretend it is: where the decoder has no name for an opcode it still gets the length right, and where it refuses it says why. The formula generalises to any variable-length ISA; the table does not, and the honest summary is that the part a machine needs is thirty lines of arithmetic, and the part a person needs is the table, the oracle, and the 118 checks that keep them honest.