4 ms·

Exploring x86-64 Instruction Encoding

84 points by kenanb 3y ago

userbinator 3y ago
Understanding x86 instruction encoding is far better done in octal --- you can memorise most of the instruction set this way: https://news.ycombinator.com/item?id=30409100 https://news.ycombinator.com/item?id=30409100 Of course, IMO the 64-bit extension by AMD that followed it was far messier.
- kenanb 3y ago
  Author here. Thanks for the link! I added the "x86 Is an Octal Machine" link, quoting your comment, in the end of my "encoding resources" post here: https://blog.kenanb.com/code/low-level/2024/01/07/x86-insn-encoding-resources.html https://blog.kenanb.com/code/low-level/2024/01/07/x86-insn-e... I have also been referencing that document since I started writing on the topic: https://blog.kenanb.com/code/low-level/2024/01/04/x86-insn-encoding.html#octal-system https://blog.kenanb.com/code/low-level/2024/01/04/x86-insn-e... 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.
  - toast0 3y ago
    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]. [1] https://www.nesdev.org/wiki/CPU_unofficial_opcodes https://www.nesdev.org/wiki/CPU_unofficial_opcodes
  - ithkuil 3y ago
    The pdp-11 was also an "octal machine" and it was clear from all the documentation that it was. When did the switch to hex happen?
  - kenanb 3y ago
    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.
xelxebar 3y ago
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: - x86 Instruction and Opcode Reference: http://ref.x86asm.net/ 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/ 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/ 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/ https://dacvs.neocities.org/SF/
- kenanb 3y ago
  Author here. Thanks a lot for the links! I was actually collecting the relevant resources in another post I published yesterday: https://blog.kenanb.com/code/low-level/2024/01/07/x86-insn-encoding-resources.html https://blog.kenanb.com/code/low-level/2024/01/07/x86-insn-e... 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. [0]: https://www.youtube.com/playlist?list=PLZCIHSjpQ12woLj0sjsnqDH8yVuXwTy3p https://www.youtube.com/playlist?list=PLZCIHSjpQ12woLj0sjsnq...
jcranmer 3y ago
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.
- kenanb 3y ago
  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. But I would have difficulty translating from one to the other, because the opcode encoding is difficult. You can actually see me intentionally handwaving it in an earlier post: https://blog.kenanb.com/code/low-level/2024/01/04/x86-insn-encoding.html#decoding-the-instruction https://blog.kenanb.com/code/low-level/2024/01/04/x86-insn-e... 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 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"
tekknolagi 3y ago
Neat post! I wrote a little bit about this too because my assembler had a bug: https://bernsteinbear.com/blog/compiling-a-lisp-10/ https://bernsteinbear.com/blog/compiling-a-lisp-10/
- kenanb 3y ago
  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. [0] https://www.youtube.com/watch?v=5FCgOFbKHYU https://www.youtube.com/watch?v=5FCgOFbKHYU [1] https://blog.kenanb.com/code/low-level/2024/01/07/x86-insn-encoding-resources.html https://blog.kenanb.com/code/low-level/2024/01/07/x86-insn-e...
myrtus 3y ago
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 https://github.com/zyantific/zydis/tree/master https://github.com/zyantific/zydis/tree/master https://www.hexacorn.com/blog/2023/09/27/zydisinfo-the-disassembler-that-breaks-the-code-twice/ https://www.hexacorn.com/blog/2023/09/27/zydisinfo-the-disas...
- kenanb 3y ago
  Looks super cool! This tells me: - The general layout of the instruction (segments). - The type and size of operands. - Where, in the instruction, each operand is encoded. I will probably use this a lot. Thanks!
sylware 3y ago
Don't be a masochist... x86_64 instruction encoding...

84 points by kenanb 3y ago

Understanding x86 instruction encoding is far better done in octal --- you can memorise most of the instruction set this way: https://news.ycombinator.com/item?id=30409100 https://news.ycombinator.com/item?id=30409100 Of course, IMO the 64-bit extension by AMD that followed it was far messier.

kenanb 3y ago
Author here. Thanks for the link! I added the "x86 Is an Octal Machine" link, quoting your comment, in the end of my "encoding resources" post here: https://blog.kenanb.com/code/low-level/2024/01/07/x86-insn-encoding-resources.html https://blog.kenanb.com/code/low-level/2024/01/07/x86-insn-e... I have also been referencing that document since I started writing on the topic: https://blog.kenanb.com/code/low-level/2024/01/04/x86-insn-encoding.html#octal-system https://blog.kenanb.com/code/low-level/2024/01/04/x86-insn-e... 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.
- toast0 3y ago
  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]. [1] https://www.nesdev.org/wiki/CPU_unofficial_opcodes https://www.nesdev.org/wiki/CPU_unofficial_opcodes
- ithkuil 3y ago
  The pdp-11 was also an "octal machine" and it was clear from all the documentation that it was. When did the switch to hex happen?
- kenanb 3y ago
  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.

xelxebar 3y ago

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: - x86 Instruction and Opcode Reference: http://ref.x86asm.net/ 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/ 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/ 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/ https://dacvs.neocities.org/SF/

kenanb 3y ago
Author here. Thanks a lot for the links! I was actually collecting the relevant resources in another post I published yesterday: https://blog.kenanb.com/code/low-level/2024/01/07/x86-insn-encoding-resources.html https://blog.kenanb.com/code/low-level/2024/01/07/x86-insn-e... 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. [0]: https://www.youtube.com/playlist?list=PLZCIHSjpQ12woLj0sjsnqDH8yVuXwTy3p https://www.youtube.com/playlist?list=PLZCIHSjpQ12woLj0sjsnq...

jcranmer 3y ago

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.

kenanb 3y ago
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. But I would have difficulty translating from one to the other, because the opcode encoding is difficult. You can actually see me intentionally handwaving it in an earlier post: https://blog.kenanb.com/code/low-level/2024/01/04/x86-insn-encoding.html#decoding-the-instruction https://blog.kenanb.com/code/low-level/2024/01/04/x86-insn-e... 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 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"

tekknolagi 3y ago

Neat post! I wrote a little bit about this too because my assembler had a bug: https://bernsteinbear.com/blog/compiling-a-lisp-10/ https://bernsteinbear.com/blog/compiling-a-lisp-10/

kenanb 3y ago
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. [0] https://www.youtube.com/watch?v=5FCgOFbKHYU https://www.youtube.com/watch?v=5FCgOFbKHYU [1] https://blog.kenanb.com/code/low-level/2024/01/07/x86-insn-encoding-resources.html https://blog.kenanb.com/code/low-level/2024/01/07/x86-insn-e...

myrtus 3y ago

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 https://github.com/zyantific/zydis/tree/master https://github.com/zyantific/zydis/tree/master https://www.hexacorn.com/blog/2023/09/27/zydisinfo-the-disassembler-that-breaks-the-code-twice/ https://www.hexacorn.com/blog/2023/09/27/zydisinfo-the-disas...

kenanb 3y ago
Looks super cool! This tells me: - The general layout of the instruction (segments). - The type and size of operands. - Where, in the instruction, each operand is encoded. I will probably use this a lot. Thanks!

sylware 3y ago

Don't be a masochist... x86_64 instruction encoding...