How do you build a virtual machine to interpret machine code?

Question

How does the parser parse the machine code? Does it go byte by byte? How does it know how many bytes to read when parsing an instruction? Does it have some sorts of tables of bytes to translate the machine code via table directly into assembly like AST?

I am starting to understand how to generate the machine code from Assembly, but how do you go from machine code to assembly essentially, from machine code to an AST used by a VM? What are the general principles?

Are there any open source projects that demonstrate this for x86? I have seem many "x86 vms" on GitHub which interpret assembly instructions, but none that interpret machine code directly. I guess this would be some sort of reverse engineering project (maybe this is one?), but not sure where to look. Even something which takes the machine code and converts it to assembly string would be valuable to see, something similar to objdump, but ideally in JavaScript/Node.js :)

This looks like a good start, is this standard?

void
xed_instruction_length_decode(xed_decoded_inst_t* ild)
{
    prefix_scanner(ild);
#if defined(XED_AVX) 
    if (xed3_operand_get_out_of_bytes(ild)) 
        return;
    vex_scanner(ild);
#endif
#if defined(XED_SUPPORTS_AVX512) || defined(XED_SUPPORTS_KNC)

    // evex scanner assumes it can read bytes so we must check for limit first.
    if (xed3_operand_get_out_of_bytes(ild))
        return;

    // if we got a vex prefix (which also sucks down the opcode),
    // then we do not need to scan for evex prefixes.
    if (!xed3_operand_get_vexvalid(ild) && chip_supports_avx512(ild)) 
        evex_scanner(ild);
#endif

    if (xed3_operand_get_out_of_bytes(ild))
        return;
#if defined(XED_AVX)
    // vex/xop prefixes also eat the vex/xop opcode
    if (!xed3_operand_get_vexvalid(ild) &&
        !xed3_operand_get_error(ild)     )
        opcode_scanner(ild);
#else
    opcode_scanner(ild);
#endif
    modrm_scanner(ild);
    sib_scanner(ild);
    disp_scanner(ild);
    imm_scanner(ild);
}

It looks like a lot of processing to figure out the instructions.

But alas, some of the functions source code are missing, like xed3_operand_get_out_of_bytes...

Answer 1

yes the parser can parse byte by byte
an x86 instruction is MAX 15 Bytes

so if it sees 15 bytes of 0x66 (PREFIX BYTE )one followed by another
it will discard 13 bytes , consider the 14th byte as VALID PREFIX and disassemble the 14th&15th byte
(same for all LEGACY_PREFIX(2e,...67) ,REX_FAMILY on x64 (0x40,0x4f)

see for a python poc

from capstone import *
CODE = [
b"\x66\x66\x66\x66\x66\x66\x66\x66\x66\x66\x66\x66\x66\x66\x90\x90",
b"\x41\x41\x41\x41\x41\x41\x41\x41\x41\x41\x41\x41\x41\x41\x90\x90",
b"\x2e\x2e\x2e\x2e\x2e\x2e\x2e\x2e\x2e\x2e\x2e\x2e\x2e\x2e\x90\x90"
]
print("\nCODE[0] parsed notice the Address of Successive instructions")
for i in (Cs(CS_ARCH_X86,CS_MODE_64).disasm(CODE[0],0x10000000)):
    print("0x%x:\t%s\t%s" %(i.address, i.mnemonic, i.op_str))
print("\nCODE[1] parsed notice the Address of Successive instructions")
for i in (Cs(CS_ARCH_X86,CS_MODE_64).disasm(CODE[1],0x10000000)):
    print("0x%x:\t%s\t%s" %(i.address, i.mnemonic, i.op_str))
print("\nCODE[2] parsed notice the Address of Successive instructions")
for i in (Cs(CS_ARCH_X86,CS_MODE_64).disasm(CODE[2],0x10000000)):
    print("0x%x:\t%s\t%s" %(i.address, i.mnemonic, i.op_str)) 


:\>python dis64.py

CODE[0] parsed notice the Address of Successive instructions
0x10000000:     nop
0x1000000f:     nop

CODE[1] parsed notice the Address of Successive instructions
0x10000000:     xchg    eax, r8d
0x1000000f:     nop

CODE[2] parsed notice the Address of Successive instructions
0x10000000:     nop
0x1000000f:     nop

parsing the opcode is complex procedure (cisc instructions for x86/x86_64)

manually decoding a random stream of bytes

a simple one byte opcode with 4 byte immediate

>>> "{0:040b}".format(0x3dffffffff)
'0011110111111111111111111111111111111111'
========================================================
  0x3d       0xff       0xff       0xff       0xff
76543210 | 76543210 | 76543210 | 76543210 | 76543210
00111101 | 11111111 | 11111111 | 11111111 | 11111111
------ds | modregrm sib immediate etc follows

simple naive parser action will be like

first 6 bits 001111  using a look up table this is a CMP mnemonic 

(0x3c,al,imm8 or 0x3d eax,imm32)

7th bit dbit = 0 a register
8th bit sbit = 1 so 32 bit register so takes a  32 bit wide immediate 

so this will be 
CMP EAX,0xffffffff

checking with some known implementations

windbg
0:000> eb . 3d ff ff ff ff;u . l 1
ntdll!LdrpDoDebuggerBreak+0x2c:
778b05a6 3dffffffff      cmp     eax,0FFFFFFFFh
0:000>

objdump
:\>echo "\x3dffffffff" | xxd -r -p > foo.bin
:\>xxd -g 1 foo.bin
00000000: 3d ff ff ff ff                                   =....
:\>objdump.exe -b binary -mi386 -D foo.bin

foo.bin:     file format binary
Disassembly of section .data:
00000000 <.data>:
   0:   3d ff ff ff ff          cmp    $0xffffffff,%eax

you can also use capstone,gdb,llvm,distorm,xed,.......as above