Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 67 ยท Instruction Set Architecture

Instruction Formats and Encoding

See how an instruction becomes bits: opcode and operand fields, R, I and J formats, fixed versus variable length, with a working encoder and decoder in Python.

To the processor, an instruction is just a number. Somewhere inside that number the hardware must find three things: which operation to perform, which registers or memory locations to use, and sometimes a constant. The instruction format is the plan that says which bits mean what, and encoding is the act of turning a human-readable instruction like add r1, r2, r3 into those bits.

Format design is a classic engineering squeeze. Every field costs bits, the instruction has a limited length, and the decoding hardware should stay simple. In this lesson you will meet the standard fields, the three formats of our teaching ISA TC16, the trade-offs between fixed and variable instruction length, and you will write a working encoder and decoder in Python.

The parts of an instruction

Almost every instruction is built from these fields:

  • Opcode: selects the operation (add, load, branch, ...).
  • Register specifiers: which registers are sources and which is the destination. With 8 registers a specifier needs 3 bits, with 32 registers 5 bits.
  • Immediate: a constant stored in the instruction itself, such as the 5 in addi r1, r1, 5.
  • Address or offset: a target for a jump, a branch distance, or a memory displacement.
  • Function code (funct): extra bits that choose one operation out of a group sharing an opcode.

An important design idea is the expanding opcode: instead of giving every instruction a unique opcode of the same size, a family of instructions that share the same layout gets one opcode and is separated by a funct field. TC16 does this for its register-to-register operations.

Instruction length is also affected by how many operands are named. Compare the styles:

Style Example Registers named
3-address add r1, r2, r3 (r1 = r2 + r3) 3
2-address add r1, r2 (r1 = r1 + r2) 2
1-address add r2 (acc = acc + r2) 1
0-address add (top two stack values) 0

Fewer named operands means shorter instructions but more instructions for the same job; you saw that trade-off in Instruction Set Architecture.

The three TC16 formats

Every TC16 instruction is exactly 16 bits and has one of three layouts. Bit 15 is the most significant.

Format 15-12 11-9 8-6 5-3 2-0 Used for
R (register) op = 0 rd rs rt funct add sub and or xor slt sll srl
I (immediate) op ra rb imm6 (bits 5-0) addi lw sw beq bne
J (jump) op addr12 (bits 11-0) j halt
flowchart TB
  W["16-bit instruction word"] --> OP{"opcode in bits 15-12"}
  OP -->|"0"| R["R format<br/>rd, rs, rt, funct"]
  OP -->|"1 to 5"| I["I format<br/>ra, rb, imm6"]
  OP -->|"6 or 15"| J["J format<br/>12-bit address"]
  OP -->|"7 to 14"| X["Unused (reserved)"]

The decoder looks at the opcode first, then slices the remaining bits according to the format.

The opcodes are: 0 for the R group, 1 addi, 2 lw, 3 sw, 4 beq, 5 bne, 6 j and 15 halt. For the R group, funct is 0 add, 1 sub, 2 and, 3 or, 4 xor, 5 slt, 6 sll, 7 srl.

Some details worth noticing:

  • The I format has only 6 bits for the immediate, which is a signed value from -32 to 31. That is small. Real ISAs face the same limit: RISC-V gives addi a 12-bit immediate and MIPS 16 bits, and loading a larger constant takes two instructions.
  • In lw and sw, the ra field is the data register and rb is the base register that holds the address; the immediate is the offset: lw r6, 12(r2) reads from the address in r2 plus 12.
  • In beq and bne, ra and rb are the two registers being compared and the immediate is a branch offset, counted in instructions from the one after the branch: the target is PC + 1 + offset.
  • The J format uses all remaining 12 bits as an address, which covers all 4,096 words of memory.

Every format keeps the opcode in the same place and the register fields in the same positions, which lets the hardware begin reading registers before it has finished decoding. That regularity is a hallmark of RISC designs.

An encoder and a decoder

Encoding is bit packing: shift each field to its position and combine with OR. Decoding is the opposite: shift and mask. A negative immediate is stored in two's complement in 6 bits, so it must be masked with & 63 on the way in and sign-extended on the way out (see Signed Integers and Two's Complement).

Python Encode and decode TC16 instructions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check the first row by hand. add r1, r2, r3 has opcode 0000, rd = 1 = 001, rs = 2 = 010, rt = 3 = 011 and funct 0 = 000. Joined together that is 0000 0010 1001 1000, which is 0x0298. The decoder reverses it exactly.

The second-to-last line of output shows something every designer notices: exactly half of all 65,536 bit patterns are valid TC16 instructions, because 8 of the 16 possible opcodes are defined. The unused patterns are reserved. A real CPU raises an "illegal instruction" exception when it meets one, and later versions of the ISA can claim them for new instructions. (Our toy decoder also ignores bits that halt and j do not use, which a real implementation might insist are zero.)

When you decode by hand, convert the hex word to binary first, split it into fields, and only then interpret each field. Reading 0x2C8C as a decimal number tells you nothing; reading it as 0010 110 010 001 100 tells you "load into r6 from address r2 + 12".

Fixed versus variable length

TC16 uses fixed-length instructions: every one is 16 bits. That has clear benefits:

  • The next instruction is always at PC + 1 word, so fetching is trivial.
  • Several instructions can be fetched and decoded in parallel without first working out where each one starts.
  • Pipelines stay simple.

The costs are that simple instructions waste bits, and large constants and addresses do not fit.

Variable-length encodings choose the size per instruction. The x86 architecture has instructions from 1 to 15 bytes. Frequent, simple operations get short encodings, so programs are smaller, and long constants can follow the opcode. The costs are complicated decoding (you must decode one instruction to know where the next begins) and harder parallel decoding.

Many RISC designs compromise. ARM's Thumb-2 and RISC-V's compressed extension mix 16-bit and 32-bit instructions, picking the short form when it fits.

The next demo decodes a made-up byte code in which the first byte determines the length: 1 byte for NOP, 2 for INC, 3 for JMP and 4 for LOAD. It also shows a danger of variable length: start reading in the wrong place and you decode garbage.

Python Decoding a variable-length byte stream

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The same ten bytes mean four sensible instructions when read from the start, and nonsense when read from byte 1. In this example the decoder happens to line up again at byte 4, but that is luck. This is why x86 disassemblers and security tools can disagree about code that jumps into the middle of an instruction. A fixed-width ISA has no such ambiguity.

Real encodings, read-only

Here are real encodings of "add two registers" on three real ISAs. The bit layouts are different but follow the same principle: opcode, register specifiers, function bits.

TEXT
RISC-V   add x1, x2, x3     0x003100B3   32 bits: funct7 | rs2 | rs1 | funct3 | rd | opcode
AArch64  add x0, x1, x2     0x8B020020   32 bits: fixed width, register fields of 5 bits
x86-64   add eax, ebx       01 D8        2 bytes: opcode 01, then a ModRM byte naming both registers
x86-64   mov rax, <64-bit>  48 B8 + 8 bytes   10 bytes: a prefix, an opcode and the full constant

The RISC-V and ARM register fields are 5 bits wide because those ISAs have 32 registers, compared with the 3 bits of TC16. That alone explains why TC16 can name three registers in nine bits.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is an expanding opcode?

    Giving a whole group of similar instructions the same opcode and distinguishing them with a funct field saves opcode space. TC16 does this for its R-format instructions.
  2. 2. In TC16, how many different values can the I-format immediate hold?

    The immediate has 6 bits, which gives 2^6 = 64 values. Read as two's complement, they range from -32 to 31.
  3. 3. Why are fixed-length instructions easier to pipeline and decode in parallel?

    With a fixed width the start of every instruction is known in advance, so several can be fetched and decoded at the same time.
  4. 4. TC16 has 8 registers. How many bits does a register specifier need?

    Naming one of 8 registers needs log2(8) = 3 bits. Three register fields therefore use 9 bits of the 16-bit word.
  5. 5. What does the word 0x0298 decode to in TC16?

    0x0298 is 0000 001 010 011 000: opcode 0 (R format), rd = 1, rs = 2, rt = 3, funct = 0 (add).

Summary

  • An instruction format divides the instruction word into fields: opcode, register specifiers, immediates, addresses and sometimes a function code.
  • TC16 has three 16-bit formats: R (three registers and funct), I (two registers and a signed 6-bit immediate) and J (a 12-bit address).
  • Encoding packs fields with shifts and OR; decoding extracts them with shifts and masks. Negative immediates need masking when encoding and sign extension when decoding.
  • Unused opcodes are reserved for illegal-instruction traps or future extensions.
  • Fixed-length encodings are simple and pipeline-friendly. Variable-length encodings give denser code at the price of harder decoding.
  • Small immediate fields force multi-instruction sequences to build large constants.

Continue with Addressing Modes.