ARM static analysis engine internals, Part 1: Disassembly opcode table design

2026-10-08

Translated by DeepSeek Flash.

Originally published in Chinese on Kanxue Forum.

Disassembly is actually pretty straightforward. For a standard ELF, PE, or Mach-O file—one without any special obfuscation—you simply locate the relevant code section and walk through it sequentially: look up the table, decode, emit the assembly. Capstone (built on LLVM), Ghidra, and Zydis all work this way. The “table” is just the CPU instruction set manual.

We implemented an ARM disassembly engine called “Rosemary.” Under the hood it works much the same way as Capstone and Zydis—in other words, we reinvented the wheel.

The engine was built from the manual DDI0487L_b_a-profile_architecture_reference_manual.pdf; I haven’t checked recently whether a newer revision has been released.

I. Instruction encoding table

The ARM instruction encoding table is structured much like a B-tree index. Take ARM64: we’re working with a 32-bit (4-byte) value.

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
|                                                             |
31                                                            0

Bits 0 through 31 are organized so that individual bits, or groups of bits, define specific categories and sections. The pattern 0xx0000xxxxxxxxxxxxxxxxxxxxxxxx, for instance, is a reserved ARM encoding; any instruction matching it can be treated as a NOP (No Operation).

At the top level, the ARM instruction encoding table is split into Reserved, SME, SVE, UNALLOCATED, Data Processing – Immediate, Branches/Exception Generating/System, Data Processing – Register, Data Processing – Scalar Floating-Point and Advanced SIMD, and Loads and Stores:

Take “Data Processing – Immediate”, for example:

The secondary encoding level is further subdivided into categories such as Data Processing (1-source), PC-relative, Add/Sub/Logic, and so on. With the manual open beside you, a given ARM instruction is easy to decode. If the binary representation is:

xxx100xxxxxxxxxxxxxxxxxxxxxxxxx # op1 == 100x

then it belongs to “Data Processing – Immediate.” If it is:

x11100111xxxxxxxxxxxxxxxxxxxxxx
# Level 1: op1 == 100x
# Level 2: op0 == 11 && op1 == 111x

then it falls under “Data Processing (1-source immediate)”, and so on down to the individual instruction.

II. Instructions

Once an instruction is matched, the next step is to work out its operands. In mov x0, 1, for example, the instruction is mov and there are two operands: x0 and the constant 1. Take the ARM64 add (Immediate) instruction:

┌────┬────┬────┬─────────────┬──────┬─────────┬──────┬──────┐
│ 31 │ 30 │ 29 │    28:23    │  22  │  21:10  │ 9:5  │ 4:0  │
├────┼────┼────┼─────────────┼──────┼─────────┼──────┼──────┤
│ sf │ op │ S  │ 1 0 0 0 1 0 │  sh  │  imm12  │  Rn  │  Rd  │
└────┴────┴────┴─────────────┴──────┴─────────┴──────┴──────┘

This add instruction has three operands—add Xd, Xn, #imm—where:

• register Xd occupies bits 0–4,
• register Xn occupies bits 5–9,
• the immediate occupies bits 10–21.

The immediate carries a shift component: if sh (bit 22) is 1, the immediate is left-shifted by 12 bits; if it is 0, no shift is applied.

The sf bit selects between 32-bit and 64-bit registers; when it is 32-bit, Xn becomes Wn. Wn and Xn share the same physical location, but they differ in length.

III. DSL

With that groundwork laid, we can design the decoder and its decoding data. The simplest—and crudest—approach would be:

switch (code) {
case xxxxx: add;
case xxxxx: sub;
case xxxxx: mov
}

But a CPU instruction set contains thousands of distinct instructions, and implementing them as one massive switch statement would be virtually unmaintainable. The standard practice, therefore, is to define a custom data format and generate the decoding table from it.

The next step is designing a data structure to describe ARM, x86, or MIPS assembly instructions. Here you can use whatever scripting language you like—Lua or Python, say—to describe the instruction set. I like writing Ruby, so Ruby it is. Take the add instruction from “Data Processing – Immediate”:

Definition:

{
  patterns: 'xxx100xxxxxxxxxxxxxxxxxxxxxxxxxx',
  desc: 'C4.1.92 Data Processing – Immediate',
  list: [
    # ...... Omitted
    {
      patterns: 'xxx100010xxxxxxxxxxxxxxxxxxxxxxx',
      desc: 'C4.1.92.3 Add/subtract (immediate)',
      funs: {
        fshift: {
          //
        },
        falias_add_mov_boolean: {
          //
        }
      },
      list: [
        {
          param: '31:0,30:0,29:0',
          name: 'add',
          grammar: 'ADD <Wd|WSP>, <Wn|WSP>, #<imm>{, <shift>}',
          ops_desc: [
            { t: :r_w, v: '0:5', wsp: true },
            { t: :r_w, v: '5:5', wsp: true },
            { t: :imm, v: '10:12', shift: { t: :lsl, v: 'f:f1' } }
          ],
          aliases: [
            {
              name: 'mov',
              cond: 'f:falias_add_mov_boolean',
              ops_desc: [
                { t: :r_w, v: '0:5', wsp: true },
                { t: :r_w, v: '5:5', wsp: true }
              ],
              dataflow: { def: [0] }
            }
          ],
          dataflow: { use: [1], def: [0] },
          semantic: { op: :add }
        },
      ]
    }
    # ...... Omitted
  ]
}

The descriptive data for an add instruction looks like this:

• patterns: describes each bit of the instruction using 0, 1, or x; 0 and 1 mark bits that must be set to 0 or 1 respectively, while x means “don’t care.”
• desc: a description string for the section, to aid debugging.
• list: marks this as a section; an entry without a list field is a single concrete instruction.
• param: written in 31:0, 30:0, 29:0 form; here it means bits 31, 30, and 29 of the instruction must all be 0.
• name: the instruction mnemonic.
• grammar: the instruction syntax, provided to make debugging easier.
• ops_desc: describes each operand of the instruction. Take add Wd, Wn, #imm, for example:
  • t: :r_w means the operand is a register; w denotes a 32-bit register and x a 64-bit register. SIMD vector registers are also supported.
  • v: '0:5' means the register index for this instruction occupies bits 0 through 4 (five bits in total).
  • wsp: true means the operand may be the stack pointer, depending on the register index.
• aliases: alternative names for the instruction. The ARM instruction set has no actual mov instruction, yet mov shows up constantly in disassembly—the result of aliasing. Aliases are conditional: when certain conditions hold, an add instruction may be aliased as mov.
• dataflow: describes the data flow of the instruction. Arrays within def and use identify operand indices. Take add:
  • def: [0] means the operand at index 0 is a definition (destination).
  • use: [1] means the operand at index 1 is a use (source).
  • Constant operands, where present, are not counted in dataflow.
• semantic: the instruction’s core semantics; for add, binary addition.

Once all this is in place, we can start on the decoder

Follow garlic on GitHub: https://github.com/neocanable/garlic