Oh, cool. This is the first time I've encountered anyone else mentioning hand decompilation of x86-64 instructions. I spent some time doing that with small binaries a while back. The original motivation was SmithForth[0].
For those interested in this kind of thing, here are some useful resources I've stumbled upon:
An library and CLI tool for encoding and decoding instructions between hex and their mnemonics. This tool gave me a fun side quest, sending upstream a patch to make the build reproducible.
- Intel Software Developer Manuals
It takes a little bit of time to get into the groove with these, but the first chapters of each volume contain excellent high-level explanations of the different moving pieces in modern x86 chips.
Excellent resource for going beyond the ISA and understanding microarchitectural details.
Anyway, I'm still quite green, but if anyone's interested in chatting about this kind of thing, feel free to ping me. Email should be in my profile description.
Intel XED was missing, so I just added that one as an update at the end, quoting your description.
I had a look at Intel XED earlier. I found it interesting but had difficulty navigating the sources. I will give it another try. Thanks!
Re SmithForth: I was just watching through the "Handmade Linux x86 Executables"[0] videos from the same person. Definitely super interesting series of work.
This reminds me of some playing around I did with x86 instruction decoding. I've sort of come to a conclusion that both the assembly and the manual are lying to you a little bit about the actual instruction formats.
The basic form of an x86 instruction is as follows:
* The presence or absence of each of 5 "legacy" prefixes (0x66, 0x67, 0xf0, 0xf2, 0xf3). Supposedly, 0xf0, 0xf2, and 0xf3 can't coexist (they're all group 1), but if you look carefully at a few instructions, it turns out that there are some instructions which require you to specify two of them at the same time.
* The group 2 prefixes end up being a segment register specifier, although they got overloaded as branch hits for the branch instructions.
* If you use a REX prefix, it adds an extra bit to the opcode (REX.w). If you use a VEX prefix, it adds two extra bits (REX.w and VEX.l). EVEX adds five extra bits (REX.w, VEX.l + EVEX.l, EVEX.b, EVEX.z). Otherwise, everything they add is extra register bits, although some instructions may have differences if they use a "modern" prefix versus not.
* Opcode map. For VEX and EVEX, you specify this via a few bits in the prefix, but otherwise, you use 0x0f, 0x0f 0x38, or 0x0f 0x3a to specify.
* 1-byte opcode.
Combine all of these together, and you almost have every unique instruction. That's roughly ~21 bits of opcode encoding (fewer due to holes and impossible encodings), and this will tell you what the instruction expects as its opcode form: whether it has a ModR/M byte and how many subsequent immediate bytes it expects. The ModR/M byte specifies a register and either a register or a memory location. It actually doesn't take that long to iterate through every single x86 instruction!
However, there's one last trick x86 plays: sometimes, the register of the ModR/M byte is used to select between different instructions, particularly when you have an instruction that only takes memory instructions. So the instruction 0x0f 0x01 with r0 is a SGDT instruction, whereas the instruction 0x0f 0x01 with r3 is a LIDT instruction instead.
Wow that's a very interesting summary of the encoding of opcode itself. Thanks!
I find this part the most challenging. It is relatively easy to figure out the "mapping between the assembly and instruction" when you have both in front of you already, as I did in my posts.
Note for other people reading both my post and the comment above:
The terms r0 and r3 in the last paragraph corresponds to what I describe in my post as: The "register code" or "opcode extension" values stored in the "ModR/M.reg" field. In this case, the values 0 and 3 are meant to be "opcode extensions". You can see both instructions here: http://ref.x86asm.net/coder64.html#x0F01 . The values 0 (for SGDT) and 3 (for LIDT) are shown in the column called "o", which is defined as: "Register/ Opcode Field"
* F0 and F2 are not mutually exclusive; there are few instructions that use both prefixes simultaneously.
* It's a little bit more helpful, IMHO, to think of the prefixes not as prefixes but as extra bits to the opcode, so 0x66 0x00 and 0x00 are different instructions that just happen to both be ADD of different sizes.
In general, the section on "legacy" prefixes seems to have largely been untouched since largely the 32-bit days, and so it's generally written as if it's mostly talking about 8086-style instructions whereas the actual implementation (especially when you start getting to the SSE instructions) has diverged somewhat from the original meanings of those prefixes, instead just stealing them for extra opcode bits.
It really helps reasoning about the encoding, but as you pointed out, x64 extension makes it challenging. I basically end up switching between octal and hex, depending on the byte, during the process.
I suspect it's similar to the 6502, picking the right arrangement and grouping of bits will make the patterns more apparent. The 6502 has a much more limited set of instructions, but here's an example of changing the arrangement [1].
Another note on this topic that in hindsight, should have been obvious, but it got me confused at the time:
Just trying to dump the whole (or large parts of the) instruction in octal will make things much more confusing. That's not what's meant by the "x86 is an octal machine" statement.
It is only individual bytes, and only certain bytes, of the instruction the should be "separately" printed in octal, to make certain patterns easier to read. If you try to print a group of bytes in octal at once, irrelevant information from adjacent byte will be bundled into a single octal digit.
This looks awesome! I really like that you have nicely organized pointers back to the reference document for each section along with diagrams!
It is also cool that this is written for the actual use-case of encoding instructions for a compiler. Being a lisper myself, I will probably start reading this series from scratch.
I also found a youtube video called "X86_64 Instruction Encoding - Compiler Programming Ep4"[0] which I added to my encoding resources[1] post.
I am hoping to add your link there as well, once I read through it.
You can visualize how instructions are encoded with zydisinfo. Pass in your architecture and the hex bytes of the instructions and it’ll show all relevant info
For those interested in this kind of thing, here are some useful resources I've stumbled upon:
- x86 Instruction and Opcode Reference: http://ref.x86asm.net/
Probably the best reference for navigating opcodes. It's extreme detail gives a good sense of x86 ISA nuances.
- Intel XED: https://intelxed.github.io/
An library and CLI tool for encoding and decoding instructions between hex and their mnemonics. This tool gave me a fun side quest, sending upstream a patch to make the build reproducible.
- Intel Software Developer Manuals
It takes a little bit of time to get into the groove with these, but the first chapters of each volume contain excellent high-level explanations of the different moving pieces in modern x86 chips.
- Agner Fog's optimization resources: https://www.agner.org/optimize/
Excellent resource for going beyond the ISA and understanding microarchitectural details.
Anyway, I'm still quite green, but if anyone's interested in chatting about this kind of thing, feel free to ping me. Email should be in my profile description.
[0]:https://dacvs.neocities.org/SF/