Super User is a question and answer site for computer enthusiasts and power users. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have seen some emulators that claim they execute, and even though they do, their source code shows they don't directly parse every 1 and 0 to determine an instruction.

My question is, if the emulator must emulate the exact opcodes that the real CPU would, wouldn't it be required to parse the correct binary opcode format of a game to emulate the CPU legitimately(or at all)?

For example, in game file I store one instruction, one byte, marked as follows:

0000 1111

My program must verify that this instruction indeed means (e.g. "add one to A register"), but wouldn't it need to check every zero and one in the text file to assure this?

Then the emulators would parse whole bytes, but whole bytes, again, are eight bits, and fluctuating patterns change operation output.

For example, 0000 1111 might mean add one to A, but 0000 1110 might mean add A with A.

share|improve this question
You're incorrectly assuming that programs have to work with separate bits. They don't – it's already taken care of by the CPU. Programs see whole bytes, and treat them as numbers. – grawity Jan 27 '14 at 21:56
But "whole bytes" have varying combinations of values. You'd have to compare that value to assure it's a correct opcode. And you can compare every single bit within a ROM file using fstream with C++. This is why I asked ... it's not that simple, as you're putting it. – user293808 Jan 27 '14 at 22:07
@grawity Each instruction of an emulator is based on an existing instruction set and opcode formatting. I realize you can parse it in hex as it is relative to the binary format (excluding the accuracy of a real 1:1 with bit toggling), but the real CPU doesn't know what "hex" means. The real CPU takes in input from current and generates an output, typically from a microprogram which alters logic gates within a circuit. Parsing hex skips that, so you'd actually not be emulating its real operations down to that level. You are also confusing the real CPU with an emulated one. Please restate info. – user293808 Jan 27 '14 at 22:22
Every opcode within an instruction set will evaluate to a whole number. An 8-bit machine will have instructions whose number value is 0 to 255. Obviously, a 16-bit machine can have a larger range of opcodes than an 8-bit. All the emulator has to do is compare the number to a list of 'known' instructions for the processor it's emulating. It will use the comparison functions of whatever language it's written in (usually c or c++) to do so. There's no need to parse bits. – codenoir Jan 27 '14 at 22:30
You're overcomplicating an issue that is in fact, quite simple. The emulator doesn't need to parse instructions "in hex" or "in binary", those are merely ways of displaying numbers for humans to read. While the instructions in memory are stored as a series of bits, software (including emulators) would be able to compare the whole instruction as a number. Checking that a char "x == 0x0F" is effectively the same as checking each bit of the number. An emulator has no need to check each bit, because the host CPU provides the instructions to do so. – Jeremy Sturdivant Jan 27 '14 at 22:35

Exposition -- trying to directly answer the question

If you are reading the source code for an emulator and it is not reading certain bits of a binary (executable) file and is still faithfully executing the code, then there are three possible outcomes:

  1. You are wrong in thinking that the emulator does not read every bit of the file, and it in fact does, and you're simply mistaken.
  2. You are correct, and the emulator is not reading every single bit, because it is able to assume certain facts about the behavior of the program it's emulating in order to not need to read every single bit to know what it needs to do (perhaps because it expects a certain game engine to be run, or a certain type of graphics API, or a certain type of sound API, etc).
  3. You are correct, and the emulator is not reading every single bit, because there are certain bits of the executable that are simply not necessary to execute the program correctly. They may be legacy "cruft", or metadata, or anything else that is simply extra fluff that doesn't actually consist of program functionality.
  4. You are correct, and the emulator is not reading every single bit, because the emulator is translating certain operations in the code into higher-level operations, and is completely bypassing the low-level, processor/hardware-specific instructions. For instance, if you are asked to mimic exactly what a person is doing in a video recording of that person performing a complicated operation, and they say "Now drill a hole in the side of the box", you would be quite tempted to stop watching the video and use your existing experience of how to drill holes in things instead of following the literal motions of the guy in the video (assuming you're equipped with a proper drill and are generally experienced in life). Similarly, if the emulator can deduce that the program is asking to draw a 32x32 image on the screen at a given set of coordinates, it can stop reading the code as soon as it understands what image it is, what format the image is in, and where to draw it -- it doesn't need to see how the emulated system is drawing it.

How emulators work

An emulator that executes code for another platform and/or CPU (for instance, wine) does things at various stages. Some stages are absolutely required for the emulator to work; other stages are optional and represent possibilities for performance optimization.

  • Required: "Parsing" the executable code (machine code, MSIL, Java bytecode, etc.) Parsing consists of:

    • Reading each bit of the executable code.
    • Understanding enough of the layout/format (syntax) and purpose (semantics) of each bit/byte (or any other discrete unit of information measurement you care to use) of the native code, in order to understand what it is doing.
    • To understand what a program says, the emulator has to understand the syntax of the binary format, and the semantics. Syntax consists of things like "we express 32-bit signed integers in Least Signed Bit format"; semantics consists of things like "when the native code contains an opcode 52, that means make a function call."
    • Mnemonic (helps you remember why this is necessary): If I've devoted myself to following a recipe, if I totally ignore that recipe and don't even read it, it is impossible that I can ever follow that recipe, unless I randomly try a bunch of things and luck into taking the same steps that the recipe would require. Similarly, unless you have a randomized Monte Carlo simulation that executes random CPU instructions until it lucks upon performing the same functionality as the program, any emulator is going to have to understand what the program says.

  • Required: "Translating" the parsed-out code (usually some sort of abstract data model, state machine, abstract syntax tree, or something like that) into either high-level commands (e.g. statements in C or Java) or low-level commands (e.g. CPU instructions for an x86 processor). High-level commands tend to be more optimal. For instance, if you analyze the code flow of a long sequence of CPU instructions and determine at a high level that what it's asking for is playing a certain MP3 file from disk, you can skip the whole instruction-level emulation and just use your native platform's MP3 decoder (which may be optimized for your processor) to play the same MP3 file. On the other hand, if you were to "trace" the execution of the emulated program as literally as possible, this would be slower and less optimal, because you would be giving up much of the optimization that you benefit from by executing instructions natively.

  • Optional: "Optimizing" and analyzing the code flow of a large swath of the emulated program code, or the entire program, to determine the full sequence of execution, and constructing a very detailed and sophisticated model of how your emulator is going to emulate this behavior with the native platform's facilities. Wine does this to some degree, but it's helped out by the fact that the code it's translating is x86-to-x86 (meaning that in both cases the CPU is the same instruction set, so all you have to do is hook up the Windows code to the foreign UNIX-based environment and let it run "natively").

Cake analogy

When considering the performance of an emulator, think about how many sheets of paper you'd need to write down instructions for yourself if you were watching someone on a video (with audio) baking a cake, in the following scenarios:

  • If you have never before in your life moved your hands or exercised any muscles in your body; (hint: you'd need thousands of sheets of paper to document the detailed steps of hand movement, hand-eye coordination, angling, velocity, position, basic techniques like grasping, holding utensils, kneading, etc.)

  • If you have basic motor control (you can walk and feed yourself), but have never before in your life prepared any food; (hint: you'd need tens of sheets of paper to document the individual steps, and would likely need lots of practice to get the hang of things like kneading and holding unfamiliar utensils, but you'd be able to document it in far less time than the previous case)

  • If you have never before in your life baked a cake, but you have done some food preparation before; (hint: you'd need a couple sheets of paper, but no more than 10; you would already be familiar with measuring ingredients, stirring, etc.)

  • If you have baked a cake many times before, and are very familiar with the process, but you don't know how to bake this particular variety/flavor of cake (hint: you might need half a sheet of paper to jot down the basic ingredients and the time it needs in the oven, and that's it).

Basically, at these increasing levels of "emulator competency", the emulator can do more higher-level things "natively" (using routines and procedures it already knows), and has to do less "tracing" (using routines and procedures that it is following literally from the emulated program).

To put this analogy in computer terms, you can imagine an emulator that emulates the actual hardware that the emulated program would run on, and faithfully "trace" the behavior of that hardware, perhaps even down to a hardware (circuitry) level; this would be very slow compared to an emulator that analyzes the program to such a level of sophistication that it understands when it's trying to play a sound file, and can "natively" play that sound file without needing to trace the emulated program's instructions to do so.

On "tracing" (a.k.a. rote mimicry) vs "native execution"

One last thing: tracing is slow mainly because you have to use lots of memory to "replicate" very detailed, intricate components of the thing you're emulating, and instead of just executing the instructions on your host CPU, you have to execute instructions which execute the instructions (see the level of indirection?), which leads to inefficiency. If you went whole-hog and emulated the physical hardware of a computer system as well as the program, you would be emulating the CPU, motherboard, sound card, etc., which in turn would "trace" the execution of the program as your emulator "traces" the execution of the CPU, and with this many levels of tracing, the whole thing would be extremely slow and cumbersome.

Here is a detailed example of where an emulator would not need to read every bit/byte of the input program to emulate it.

Let's say that we know of an API written in C or C++ (the details are not important) for an emulated software environment, where this API has a function void playSound(string fileName). Let's say we know that the semantics of this function is to open up the file on disk, read its contents, figure out what encoding the file is in (MP3? WAV? something else?), then to play it out the speakers at the ordinary/expected sample rate and pitch. If we read, from the native code, a set of instructions that says "enter into the playSound routine to begin playing sound /home/hello/foo.mp3", we can stop reading the program code right there, and use our own (optimized!) routine for natively opening that sound file and playing it. Do we need to follow the emulated processor on an instruction level? No, we really don't, not if we trust that we know what the API does.

A wild difference arises! (trouble in high-level land)

Of course, by reading a bunch of instructions and "inferring" a high-level execution plan, as in the example above, you run the risk that you might not precisely mimic the behavior of the original program running on the original hardware. Say for example, the original hardware might've had hardware limitations that only allowed it to play 8 sound files simultaneously. Well, if your new-fangled computer can play 128 sound files simultaneously just fine, and you are emulating the playSound routine at a high level, what's to stop you from playing more than 8 sound files at a time? This could cause... strange behavior (for better or worse) in the emulated version of the program. These cases can be resolved by careful testing, or perhaps by understanding the original execution environment really well.

For example, DOSBox has a feature that lets you intentionally limit the execution speed of the emulated DOS program, because some DOS programs would run incorrectly if they were allowed to run at full speed; they actually depended on the timing of the CPU's clock rate to execute at the expected speed. This type of "feature" that intentionally limits the execution environment can be used to provide a good tradeoff between faithfulness of execution (that is, making the emulated program work properly) and efficiency of execution (that is, constructing a representation of the program that's high-level enough that it can be efficiently emulated with a minimum of tracing).

share|improve this answer
I feel I should point out that Wine Is Not an Emulator ;) – Jeremy Sturdivant Jan 27 '14 at 22:36
Ah, but it is! Just a very efficient one, and not an x86 instruction emulator, but rather, a Windows operating environment emulator. It's certainly an emulator at some level, but not at the level people typically think of when they hear the term "emulator" (most people think of running literal CPU instructions of a foreign CPU ABI, which is just one possibility of many types/levels of emulator). – allquixotic Jan 27 '14 at 22:45
Indeed you are correct, and in fact the original meaning of the name "wine" was "WINdows Emulator", however the project's name is currently the recursive acronym given above, regardless of its accuracy. – Jeremy Sturdivant Jan 27 '14 at 22:48

My question is, if the emulator must emulate the exact opcodes that the real CPU would, wouldn't it be required to parse the correct binary opcode format of a game to emulate the CPU legitimately(or at all)?

"Parse" means "go through text and figure out what stuff means." Text and language-like syntax is complex because not only do individual "words" mean things, but the meaning can change according to their position and proximity to other words.

Probably the more accurate term to apply with regard to what a CPU does to an instruction stream (which is a lot simpler than parsing) is "decode" - and yes, an emulator must "decode" instructions in the same way. I guess "parsing" isn't really all that bad of a term, though, given the complexity of the x86 instruction set if you are talking about that.

My program must verify that this instruction indeed means (e.g. "add one to A register"), but wouldn't it need to check every zero and one in the text file to assure this?

CPUs don't really verify instructions. Any CPU has an internal register that points to a memory location in RAM. The CPU reads it, reads a couple more bytes if needed, and then tries to execute it. Modern CPUs will start an "exception process" if the instruction is an illegal one.

Old CPUs, like the old 8-bit 6502, did not even do that - some illegal instructions would lock up the CPU, others would do strange, undocumented things. (Some searching will reveal a number of undocumented x86 instructions found throughout all the CPUs in the x86 pantheon - for example, the CPUID instruction existed on some 486 CPUs before Intel officially documented it.)

A good and accurate CPU emulator is just going to chew on an instruction stream blindly like a real CPU does - though it may do different things on conditions that would cause a system lockup, like display a dialog box telling you your virtual CPU is dead instead of locking up your emulator.

Furthermore, you say "it need to check every zero and one in the text file" but typically you do not feed emulators text files. A CPU emulator needs emulated memory - and since many platforms use memory-mapped I/O, emulated I/O devices as well. Emulating things like the firmware requires you have binary images of that firmware - either legal copies of real firmware or substitute open source firmware. Emulating an entire platform (such as the "PC platform" of which the x86 CPU is a component thereof) requires more than CPU emulation.

share|improve this answer
Of course, because of the unsolvability of the Halting Problem, it is impossible that, with the virtual CPU performing any sequence of arbitrary instructions, that the host CPU would in all cases be able to prevent it from locking up, because the host can't determine whether the virtual CPU will halt unless it itself traces the virtual CPU's code, in which case, the host may not halt (basically it's sucked down the infinite-singularity rabbit hole alongside the virtual CPU as a law of information theory). :) – allquixotic Jan 27 '14 at 23:12
You can do some "hackish" things like telling your emulator to ignore CPU exceptions and what not. But then your emulator is no longer 100% accurate. – LawrenceC Jan 27 '14 at 23:15

You must log in to answer this question.