How to manually build a jump table

[*DEAD*]

Hi, im writing a 4719 emulator, which has 16 instructions. I want to make what would equate to a switch statement in c. Problem is though that i want to build the jump table at runtime.

So if i have something like this in my code

Code Select Expand

  JumpTableTerminate:
  mov eax, edx
  JumpTableAdd:
just for examples sake. But if i try to make a jmptable in the .data section those labels are undefined.

Code Select Expand

jumptable dd JumpTableTerminate, JumpTableAdd
How would i go about doing this. Thanks

[ic2]

I know nothing about the jump table or 16bit code.  I got away from it for a minute (32bit).   If this is 16bit code do it use some type of GetProcAddr stand along code.  Search the forum.  It's so easy not to when you are new.  I see stuff about emulator here some where.  Use the Advance Search Line.  Also there's  16 bit DOS Programming Forum here on the Home page.  Check it out and get some ideas.

[*DEAD*]

i have searched, there are only vague mentions of jump tables. I am writing 32 bit code, the "16 instructions" refers to the fact that the 4 bit processor has 16 different instructions, and that it makes sense to use a "switch" statement. Right now im going like this.

Code Select Expand


        cmp eax, 0
            je InstructionCaseTerminate
        cmp eax, 1
            je InstructionCaseAdd
        cmp eax, 2
            je InstructionCaseSub
        cmp eax, 3
            je InstructionCaseIncR0
        cmp eax, 4
            je InstructionCaseIncR1
        cmp eax, 5
            je InstructionCaseDecR0
        cmp eax, 6
            je InstructionCaseDecR1
        cmp eax, 7
            je InstructionCaseBeep
        cmp eax, 8
            je InstructionCasePrint
        cmp eax, 9
            je InstructionCaseLoadToR0
        cmp eax, 10
            je InstructionCaseLoadToR1
        cmp eax, 11
            je InstructionCaseLoadFromR0
        cmp eax, 12
            je InstructionCaseLoadFromR1
        cmp eax, 13
            je InstructionCaseJMP
        cmp eax, 14
            je InstructionCaseJZ
        cmp eax, 15
            je InstructionCaseJNZ

It has to be maximally efficient because im planning to bruteforce every combination of bytes up to 12 bytes to determine the longest possible finite output string for code limited to n bytes.

[jj2007]

Here is a fully functional example of a) a jumpt table and b) the SWITCH macro - but I must admit I did not quite understand what you want...

Code Select Expand


.nolist
include \masm32\include\masm32rt.inc

.data?
jt dd 16 dup (?)
switchnum dd ?

.code

AppName db "Test app", 0
BuildJumpTable dd 1

start:
  mov switchnum, 2
  .if BuildJumpTable
mov edx, offset jt
mov eax, offset Proc1
mov [edx], eax
add edx, 4
mov eax, offset Proc2
mov [edx], eax
add edx, 4
mov eax, offset Proc3
mov [edx], eax
add edx, 4

mov eax, switchnum
add eax, eax
add eax, eax
mov edx, offset jt
mov ecx, [edx+eax]
call ecx

invoke MessageBox, NULL, chr$("Was your jumptable working?"), addr AppName, MB_YESNOCANCEL

  .else
switch switchnum
case 1
call Proc1

case 2
call Proc2

case 3
call Proc3

default
invoke MessageBox, NULL, str$(switchnum), addr AppName, MB_YESNOCANCEL
endsw

invoke MessageBox, NULL, chr$("Was your switch working?"), addr AppName, MB_YESNOCANCEL

  .endif

invoke ExitProcess, eax

Proc1 proc
invoke MessageBox, NULL, str$(switchnum), addr AppName, MB_OK
ret
Proc1 endp

Proc2 proc
invoke MessageBox, NULL, str$(switchnum), addr AppName, MB_OK
ret
Proc2 endp

Proc3 proc
invoke MessageBox, NULL, str$(switchnum), addr AppName, MB_OK
ret
Proc3 endp

end start


[zooba]

If your labels (JumpTableTerminate, JumpTableAdd, etc.) are inside a PROC then they will not be visible outside that PROC. This is probably why you get the error you mentioned in your original post.

There are three solutions:

1. Define your labels (within a PROC) using a double colon.

Code Select Expand

JumpTableTerminate::

This will make the label visible everywhere throughout your code.

2. Define your labels outside of a PROC. There is no reason why all your code has to be within a procedure in MASM - you can write code wherever you like (in the .code section) and if you have some way of calling it (ie. a label) you can use it.

Alternatively, you can define your labels as PROCs.

3. Define your jump table within the PROC containing the labels.

Code Select Expand

MyProc PROC
.data
    jumptable DWORD JumpTableTerminate, JumpTableAdd
.code

...

JumpTableTerminate:

JumpTableAdd:


Here the labels are in the same scope as the jump table. Exactly what this will do to the scope of jumptable I'm not sure, I tend to avoid this solution and use the second one.

Cheers,

Zooba :U

[BogdanOntanu]

If you only have 16 IFs THEN they are faster than a switch / jump table. I have experienced a little with jump tables versus IFs and contrary to popular belief jump tables are not faster than a series of IF's. Not unless you have a huge amount of IFs that is.

The reason for this is somehow related to the fact that the CPU can not predict where a jump table with continue execution but it does predict a little about the IFs.

Bottom line is: do some hands on experiments because LOGIC is not going to work. It is not going to work simply because your do not have all of the information about the internal workings of the CPU. Of course there is a logical explanation for everything but you are not going to find it without the full blown blueprints of the CPU you are using.

Hence your only chance to find the best solution are experiments on your exact code and accurate measurements... doubled by logic close behind.

Oh and from my experience small experiments do not scale well on huge programs hence you will have to test the full blown real code.

Besides.... the fact that you write a virtual CPU pretty much kills any chance of speed what so ever... hence talking of speed on a virtual machine is secondary to other benefits you seek.

To build you jump table is simple:

Code Select Expand


.data
my_jtable:
dd offset proc_for_case_1
dd offset proc_for_case_2
...
.code

mov esi, offset my_jmp_table
mov eax,[case_code]
mov eax,[esi + 4*eax]
call eax
...


[*DEAD*]

If you only have 16 IFs THEN they are faster than a switch / jump table. I have experienced a little with jump tables versus IFs and contrary to popular belief jump tables are not faster than a series of IF's. Not unless you have a huge amount of IFs that is.

The reason for this is somehow related to the fact that the CPU can not predict where a jump table with continue execution but it does predict a little about the IFs.

Bottom line is: do some hands on experiments because LOGIC is not going to work. It is not going to work simply because your do not have all of the information about the internal workings of the CPU. Of course there is a logical explanation for everything but you are not going to find it without the full blown blueprints of the CPU you are using.

Hence your only chance to find the best solution are experiments on your exact code and accurate measurements... doubled by logic close behind.

Oh and from my experience small experiments do not scale well on huge programs hence you will have to test the full blown real code.

Besides.... the fact that you write a virtual CPU pretty much kills any chance of speed what so ever... hence talking of speed on a virtual machine is secondary to other benefits you seek.

To build you jump table is simple:

Code Select Expand


.data
my_jtable:
dd offset proc_for_case_1
dd offset proc_for_case_2
...
.code

mov esi, offset my_jmp_table
mov eax,[case_code]
mov eax,[esi + 4*eax]
call eax
...


wholly crap, i would have never have figured that.

[hutch--]

DEAD,

Have a look at a toy in the masm32 project called "tproc.exe", it is designed to make jump tables of one particular type. I am inclined to agree with Bogdan here that with a count of 16 instructions an IF block is probably fast enough and easy enough to code. If it is simply word matching to line up instructions with the opcode processing you have in mind, look at the "switch$" macro in masm32 as it is ery clear and reasonably fast code that it produces.

[Rockoon]

Also realize that at worst, the first case test within a 16 element switch should succeed no less than 1/16th of the time (there is always a case ordering that is equal or better) In practice, that first test should succeed much more often.

P4's should have the worst time with jump tables, due to the huge depth of its pipeline. Figure at least 20+ cycle latency on the jump...