5 ms·
> An x86 instruction can theoretically have an unbounded number of prefixes All x86 instructions are strongly bounded by 15 byte lengths, otherwise processors
by dragontamer 6y ago
> An x86 instruction can theoretically have an unbounded number of prefixes
All x86 instructions are strongly bounded by 15 byte lengths, otherwise processors throw an exception.
I just searched StackOverflow: https://stackoverflow.com/questions/23788236/get-size-of-assembly-instructions/23843450#23843450 https://stackoverflow.com/questions/23788236/get-size-of-ass...
Just as I expected: finite-state machine used to decode. Now write a FSM-compiler (which is an undergrad-level project), to automatically parallelize the implementation.
The parallelization step is probably Master's level, but a very advanced undergrad student can probably accomplish it: since all the individual elements are undergrad projects (Kogge-stone applied to associative operators, finite-state machine compiler / regular expressions)
The overall process is also documented by Intel in their Opcode map: https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-software-developer-instruction-set-reference-manual-325383.pdf https://www.intel.com/content/dam/www/public/us/en/documents...
As a FSM, verification is simple. Just generate all x86 instructions (there are a finite number of them after all), and ensure your FSM properly goes through all of them.
- mhh__ 6y agoThat state machine looks ahead more than one symbol and has a lot of memory even if you consider it one big state. You have to verify it decodes invalid instructions as a fault which means testing the entire search space. Hypothetically you could use a bounded model check but you need to test roughly 10^36 combinations which is still thousands of years if you can do a 1000 billion billion a second. You need a formal proof of the operation too.
- dragontamer 6y agoYou can formally verify a finite state machine by simply testing all state-transitions. You don't need to do an exhaustive check of the 2^8^15 all 15-byte combinations. You just check all state-transitions of the state machine. Or to put it another way: you don't need to test all 2^8^15 byte combinations. You just need to check all invalid-instructions that have ONE invalid byte, to prove the attributes of the finite-state-machine.