How do you code an emulator?

[Karlos]

Can someone explain the principles of writing an emulator?

Usually, start with the CPU. For that, at the simplest level you create a data structure that represents your emulated CPU (all the registers etc).

You then write code to fetch instructions from wherever the emulated PC (program counter) is pointing, decode their operands (if any), do whatever the emulated instruction does and update the data in your structure and any "emulated" memory region that would be altered accordingly. You do this in a loop until a certain number of instructions have been executed or some special condition (an interrupt or whatever) is set.

There are 2 basic ways to write that type interpreter. One uses a big switch/case construct for every possible instruction opcode. The other uses a table of function pointers which are indexed by opcode value. Each has advantages and disadvantages.

If you know your emulated CPU and target CPU very well, you may be able to write a JIT. It's rather more complicated, however.

[Karlos]

It sounds more tedious than difficult. Thanks for the info.

As a learning exercise, I wrote a simple VM entirely from scratch that implements a RISC-like instruction set, working on 16 completely general purpose 64-bit registers. Main deviations from a real CPU were:

1) A register can hold either integer, pointer or floating point data. How the data in a register were interpreted was entirely a consequence of the instruction invoked.

2) No condition codes. Instead, instructions that test either rA!=rB, rA==rB, rA>=rB, rA>rB and then branch conditionally were implemented for each supported datatype. The corresponding rA or >= test.

3) Separate stacks for register push (always 64-bit), call/return and general purpose data. Probably not ideal, but a lot easier to debug.

The machine was purely interpretive. Generally, most instructions were 2-byte entities, one byte for the operation code and 1 byte a pair of 4-bit register indexes packed together. No operations could directly modify memory, only register to register arithmetic/logic was possible. This constraint allowed the code to work on big and little endian targets without a great deal of hassle.

The lessons learned from this were that despite the simplicity of the architecture, a "register" based VM doesn't make a lot of sense, except on architectures where you can do a decent level of register mapping.

If I were to do it again, I'd use only a couple of vm registers and rely on indexable stack frames instead. I think I'd also make it have direct support for certain higher level language constructs, such as strings and arrays perhaps in general (by which I mean instructions that can apply an operation to every element in an array).

[Karlos]

Jump tables... wow this takes me back

The fastest jumptable I ever managed was one which was implemented in assembler. The handling code for each opcode had to align to and fit into 64 bytes (with branches out and back if needed for complex ops), including the code required to fetch the next opcode, which was inlined at the end of each handler. In that code, instead of actually looking up the address in a table, you just took the opcode value, left shifted it by 6 and jumped straight to the handling code via jmp (aN, dN), where aN held the address of the first handler. So in essence, you didn't really have a loop, you just had a branching frenzy, but in a relatively small are of code space. By moving to 128-byte alignment, there was no need to "branch out" for any of the handlers, but the overall performance suffered due to the fact that less of the handling code would fit into the cache on the 040. 64 was the compromise, about 90% of all the handlers fit completely in that constraint.

I couldn't really see any obvious way to make an interpreter any quicker.

[Karlos]

That's pretty much the fastest pure interpreter method there is. You can get fairly close to this with certain versions of gcc using computed goto. You'll probably end up with an extra layer of indirection in the final code compared to the assembly approach you mention, but it's still pretty fast. Rather than an array of function pointers you have an array of label addresses. Unfortunately, not only is this dependent on a non-standard gcc extension, it doesn't even produce good code in reasonably recent versions of gcc when optimizations are turned on.

The next best thing is to stick a switch statement with a bunch of gotos in a macro and then call that macro wherever you would have used goto. You end up with an unnecessary range check, but otherwise the code generated is pretty much the same. It seems more resistant to gcc's optimizer screwing it up and works in MSVC (and presumably a number of other compilers).

Out of curiousity, Karlos, what CPU were you emulating in that example of yours?

None, it was a proof of concept virtual machine. I have half implemented a z80 along similar lines though.

[Karlos]

:lol:

I forgot I'd actually bothered to make some documentation for that VM:

Here

It probably isn't up to date, regardless of what the date appears to say.