CODEWITHSUNDEEP
algorithmparsingvm-implementation
Josh Pearce
Josh Pearce

Reputation: 3455

Efficient Algorithm for Parsing OpCodes

Let's say I'm writing a virtual machine. I read in the program data into an array of bytes. Now I need to loop through those bytes (instructions are two bytes) and instantiate a little class representing each instruction and it's arguments.

What would be a fast parsing approach? Here are the two way's I've thought of:

  1. Logically branching by inspecting each bit from the left to the right until I narrowed it down to a particular op code. This would be like a binary search.
  2. Inspecting some programs to come up with a list of opcodes ordered by frequency of use, and then checking the for the full opcode in that order.

Note: I will be using bit shifting and masking in C to check, not regexes or string comps or anything high-level like that.

Upvotes: 0

Views: 1131

Answers (1)

Tyler Durden
Tyler Durden

Reputation: 11558

You don't need to parse anything. If this is in C, you make a table of function pointers which has 256 entries in it, one for each possible byte value, then jump to the appropriate function based on the first byte value. If the second byte is significant then a switch statement can be used within the function to handle the second byte. This is how the original Visual Basic interpreter (versions 1-6) worked.

Upvotes: 2

Related Questions