Make a data structure with an opcode's code and a function pointer to the opcode's operation. Sort an array of those structures by opcode. Every time you get an opcode at runtime, do a binary search on the array and, if the opcode is found, call the function pointer with the opcode's arguments (if any). If the opcode is not found, you know what to do.
Store an array for function pointers indexed by the opcode which calls them. #define EAT 0x00 #define FUCK 0x01 #define DIE 0x02 #define INSTRUCTIONS 0x03 void eat(){} void fuck(){} void die(){} int main(int a, char ** b){ void (*i[3])(); i[EAT]=eat; i[FUCK]=fuck; i[DIE]=die; while(peakNextInstruction() < INSTRUCTIONS){ i[popNextInstruction()](); } return -1; }
And having the mind of a 13 year old is also a sign of apping ability.
Name:
Anonymous2014-06-10 1:50
>>3 switch is not constant. Its upper bound is N. If the opcode being executed is the last opcode in your switch, you need to make N, or in this case 40, comparisons, whereas lg(40) = 5.
A switch would be better if you know that certain opcodes will be executed from frequently than others, in which case you can order your switch by the frequency of the opcode.
You should really inspect resulting assembly, before making any dicision.
Name:
Anonymous2014-06-10 1:59
>>9 You should inspect my anus before making any incision.
Name:
Anonymous2014-06-10 3:38
>>8-10 it's funny because while switch can be very easily implemented O(1) or very close to it (ex O(log n)) MS Visual C++tm Enterprise edition uses O(n)
How would one go about making a virtual machine without using a huge and clumsy switch( opcode ) statement?
you can use a array with function pointers but I remember some other ways too another way is to have a huge and clumsy switch but let the preprocessor handle it (just like I did) I had made a script in bash and with the help of the preprocessor I had made it so it will map every opcode in a switch statement to a function or some lines of code while I do not give it a list of the functions (the were in another file and the list was generated by the script in the stile X(functionName, something, somethingElse) and was used by many parts of my program sorry if I am not understandable, I am sleepy
Name:
Anonymous2014-06-10 4:55
Can you guys explain how switch can be implemented in O(1)? Not only I stand in disbelief of this fact, I also don't understand the wikipedia page.
Name:
Anonymous2014-06-10 5:09
>>11 Sure, you save a lot of space on transient switches that way.
>>12 The input to the switch effectively becomes an index into a lookup table of branch targets. Array lookup is O(1), as is the branch.
Name:
Anonymous2014-06-10 6:46
>>9 gcc -O2 with sequential case values and more than 3 cases will generate a jump table. If you care so very much you could also use an explicitly computed goto (assuming your compiler supports it).
Using a call table (i.e., with function pointers) is not a good idea for simple opcodes since most compilers are not smart enough to inline any of the called functions once their address is taken (even if scope of the functions and the resulting address is non-global).
tl;dr get off your high horse and use a switch/case. If it's good enough for bpf-jit it's good enough for you.
switch (e) { case INVALID_OPCODE: fprintf(stderr, "invalid opcode: %d\n", cpu.mem[cpu.ip]); return EXIT_FAILURE; case ARITY: fprintf(stderr, "invalid arity to op %d\n", cpu.mem[cpu.ip]); return EXIT_FAILURE; case SUCCESS: printf("%d %d\n", b[0], b[1]); return 0; default: fprintf(stderr, "TELL DA RETOID WHO WROTE DIS EMULATOR 2 REED" " DA FUKIN STANDARD.\n"); return EXIT_FAILURE; } }
Name:
L. A. Calculus!jYCj6s4P.g2014-06-10 7:27
O BTW, I WUD HAV COMMENTED IT, BUT I WAS AFRAID DAT IF ID HAVE DONE DAT, U RETOIDS WUD START BITCHING ABOUT HOW COMMENTS DELAY DA COMPILATION TIME BY A FEW FUKIN NANOSECONDS.
>>27 Oops, I misread the OP. Thought they were writing a virtual machine in DCPU-16 assembly, but they were actually talking about DCPU-16 emulator for PCs.
Yeah, a switch statement is the best you can do in portable C. You can get something close to token-threaded code if you use the gcc labels-as-values extension, but then it won't be portable to all C compilers, and the code generated by even the best C compiler is going to be shit compared to a naive assembly implementation.
>>19 In the beginning there were only int and char,
>>25 I find that sort of usage annoying since it will trigger "enum constant not covered" warnings in switch statements. One of many annoyances with enums in C... (I'll confess I (ab)use them frequently, solely because it makes it easy to traverse definitions with ctags.)
I prefer this ENTERPRISE QUALITY ENUM HANDING:
#include <errno.h>
typedef enum { /* yes typedef, I hate typing "enum" */ FOO, BAR, BAZ, QUX, } meta meta_t; /* and the POSIX committee can bite me */
int dispatch_meta(meta_t val) { switch (val) { case FOO: return do_foo(); case BAR: return do_bar(); case BAZ: return do_baz(); case QUX: return do_qux(); }
-typedef enum { /* yes typedef, I hate typing enum */ +typedef enum meta { /* yes typedef, I hate typing enum */ FOO, BAR, BAZ, QUX, -} meta meta_t; /* and the POSIX commitee can bite me */ +} meta_t; /* and the POSIX commitee can bite me */
-static void do_foo(); -static void do_bar(); -static void do_baz(); -static void do_qux(); +static int do_foo(); +static int do_bar(); +static int do_baz(); +static int do_qux();
>>1 You can replace the switch block with if...else if...else if...else, but that's not really a solution. Another option is to implement the instructions as functions and use an array of function pointers (i.e. opcode 5 is the function stored in instructions[5]).
Essentially though, the construct you want is the old ON OPCODE GOTO 100, 200, 300, 400, 500, and the switch statement is the closest thing C has to that.
Not at all. It's just that you're using less verbose code, and it reads cleaner, IMHO, which counts for a lot.
Name:
Anonymous2016-10-25 20:20
write it in assembly code instead of c.
then you can compute your jumps with arithemtic!
Name:
Anonymous2016-10-26 1:05
So when I write a big switch with like 100 or so branches, like this: switch(op) { case 0: /*...*/ break; case 1: /*...*/ break; case 2: /*...*/ break; case 3: /*...*/ break; ... case 100: /*...*/ break; } with the conditions always incrementing and being in order, won't a modern compiler optimize it for me?
>>52 Why wouldn't branch prediction apply to switch statements? They're still just conditional jumps in machine code.
Name:
Anonymous2016-10-26 3:14
>>54 It is harder to predict table[opcode]() than to predict if (opcode==1) {...} else {...}. Unconditional jump can be predicted only when it usually resolves to some single function.
Name:
Anonymous2016-10-26 4:09
>>54 he's an idiot/liar. nothing he says is correct. He's just guessing to try to sound smart at the smart peoples table (/prog/).
This shit never used to happen on old /prog/, we just knew that everybody only spoke when they had something of value to contribute and nobody would recommend anything if they had not actually done it themselves and performed the measurements.
Todays nu-/prog/ is full of the same cancer that filled up IRC channels on freenode. Casuals that make 'witty' little remarks with no content to look smart in front of everybody else. The real wizards are long gone. What a tragedy.
>>53 Yeah, I've already seen that. I just prefer to write C89, not GNU C. But the article does indeed explain my question: apparently switch has to do some additional bounds checking (C89 3.6.4.2).
Name:
Cudder !cXCudderUE2016-10-26 10:59
>>45 That is what those infected with the disease of ENTERPRISE will seriously say.
Just use a switch. 35-40 cases is not at all large for a switch. Many 8-bit emulators will have 256, and the VNVM I'm analysing at the moment has around 270.
>>61 Considering the C89 standard requires up to 257 (default + one for each byte, think of state machines), and C99 increased that to 1023 (no idea of the rationale for that one), 40 is certainly not large at all. C++ increased that even more to 16K(!)
Probably related to the compiler having to store a jump table with that much entries, not byte size.
C++ increased that [...] to 16K
That's just wasteful. Remember that a C89 compiler can be implemented for a machine with like 1MiB of RAM (probably the biggest culprit: #defines: up to 1024*(499+31) bytes).
Remember that a C89 compiler can be implemented for a machine with like 1MiB of RAM
A PL/I compiler can run in 32 KB of RAM and the compiled programs can run on even smaller machines. I'd rather use PL/I than any C-based or dynamically typed language any day.