Author Topic: Creating a jump table with 32-bit instructions  (Read 22719 times)

Offline mik3ca

  • Jr. Member
  • *
  • Posts: 30
Creating a jump table with 32-bit instructions
« on: January 11, 2021, 06:53:25 PM »
I'm trying to use nasm to create a jump table so I don't have to slow down the processor as it iterates through a bunch of compares. For simplicity, we will use register AL here as the value returned from an earlier user input function.

Let's say for example I have this code to process the input:

Code: [Select]
cmp AL,00h
je doitem0
cmp AL,01h
je doitem1
cmp AL,02h
je doitem2
cmp AL,03h
je doitem3
cmp AL,04h
je doitem4
.....
cmp AL,11h
je doitem17

I have attempted to convert it to something like this:

Code: [Select]
blk equ 8h ;code block size so jump code fits nicely
mov AH,0h
shl AL,3 ;shift 3x = multiply by block size
add AX,jt
jmp AX

;start of jump table
jt:
org jt+blk*0h
jmp doitem0
org jt+blk*1h
jmp doitem1
org jt+blk*2h
jmp doitem2
org jt+blk*3h
jmp doitem3
...
org jt+blk*11h
jmp doitem17

However nasm 2.10.04 (the version I have) is fussy on the second idea. For every org statement, I get the error:

Code: [Select]
      error: org value must be a critical expression

So if it doesn't like the way I'm using the org statement, is there another way I can make an efficient jump table so that the program doesn't have to have the tedious task of comparing the input to up to 16 different values  to reach the user's choice?

Offline fredericopissarra

  • Full Member
  • **
  • Posts: 374
  • Country: br
Re: Creating a jump table with 32-bit instructions
« Reply #1 on: January 11, 2021, 07:34:34 PM »
16, 32 or 64 bits code?
And what you'll do if AL > 0x11?
« Last Edit: January 11, 2021, 07:36:08 PM by fredericopissarra »

Offline fredericopissarra

  • Full Member
  • **
  • Posts: 374
  • Country: br
Re: Creating a jump table with 32-bit instructions
« Reply #2 on: January 11, 2021, 07:53:06 PM »
I'll suppose you are dealing with 32 bits code here...

Code: [Select]
  section .rodata

jmptbl:
  dd  doSomerhing0
  dd  doSomething1
  dd  doSomerhing2
  dd  doSomething3
  dd  doSomerhing4
  ...
  dd  doSomerhing14
  dd  doSomething15
  dd  doSomerhing16
  dd  doSomething17
  ...

  section .text
  ...
  cmp al,0x11
  ja  doNothing
  movzx eax,al
  jmp [jmptbl+eax*4]
doNothing:
  ...

Offline debs3759

  • Global Moderator
  • Full Member
  • *****
  • Posts: 224
  • Country: gb
    • GPUZoo
Re: Creating a jump table with 32-bit instructions
« Reply #3 on: January 11, 2021, 07:55:56 PM »
Assuming 32-bit code:

Code: [Select]
cmp     AL,11h
jg      error ; if value in al is too high, go to error routine
movzx   EAX,AL
jmp     [EAX*4 + jmptable]



jmptable: dd doitem0, doitem1, .... doitem17

« Last Edit: January 11, 2021, 07:59:19 PM by debs3759 »
My graphics card database: www.gpuzoo.com

Offline mik3ca

  • Jr. Member
  • *
  • Posts: 30
Re: Creating a jump table with 32-bit instructions
« Reply #4 on: January 11, 2021, 09:23:21 PM »
oh....
but would the idea of loading the pointer like that also work in a 16-bit environment? because I managed to isolate the code under segment CS and the offset can be anywhere from 0 to 65535 and all functions are within the same 64K. In fact they're in the same 2K since my code side when compiled is under 2K.

I wonder if I could get away with this:

I'm also looking at reducing code size as well.

Code: [Select]
mov BX,AX
shl BX,2
jmp [CS:BX+table]

table:
dw option1
dw option2
dw option3
dw option4
....
dw option17

Offline debs3759

  • Global Moderator
  • Full Member
  • *****
  • Posts: 224
  • Country: gb
    • GPUZoo
Re: Creating a jump table with 32-bit instructions
« Reply #5 on: January 11, 2021, 11:46:22 PM »
Yes, for 16-bit code you just use AX instead of EAX.

I highly recommend the error check we both put in there. The way you rewrote it is more complex than how we wrote it - you are using three lines of code to do what we did in two. In the long run, across a more complex file, things like that slow your program by adding unnecessary code. What you coded will work if you can guarantee never accidentally adding an error.
My graphics card database: www.gpuzoo.com

Offline fredericopissarra

  • Full Member
  • **
  • Posts: 374
  • Country: br
Re: Creating a jump table with 32-bit instructions
« Reply #6 on: January 12, 2021, 12:03:34 AM »
Yes, for 16-bit code you just use AX instead of EAX.

Unfortunately, not...

In 16 bits code (without using E?? registers) que effective addres can use only BX (using DS as default segment) and BP (using SS), and SI or DI for index... And, there is no scaling in 16 bits code. You can, of corse use E?? registers in 16 bits code, with scaling...


Offline fredericopissarra

  • Full Member
  • **
  • Posts: 374
  • Country: br
Re: Creating a jump table with 32-bit instructions
« Reply #7 on: January 12, 2021, 12:21:17 AM »
but would the idea of loading the pointer like that also work in a 16-bit environment?

Yes but carefully... Since 16 bits code has the limit of 64 KiB per segment, if the destinations are in other segments you need to do a "far jump", and store segment:offset pairs in your table. Supose we have 4 functions only in 4 different segments:
Code: [Select]
  cmp al,11
  ja  .doNothing
  xor ah,ah
  mov cl,2
  shl ax,cl    ; strict 16 bits code don't accept arbitrary # of shifts,
               ; unless using cl as operand.
  mov bx,ax    ; must use bx as base address.
  jmp far [cs:bx+jmptable]
.doNothing:
  ...
jmptable:
  dw func1offset, func1segment
  dw func2offset, func2segment
  dw func3offset, func3segment
  ...
If all your functions are in the same segment as the one doing the jump (CS) you only need the offsets in the table and a intrasegment jump (without the 'far'), and must change the shl ax,cl to shl ax,1 and get rid of CL.

PS: CS: override is needed only with your table is in code segment and not in data segment (the default).

And in 16 bit code you can use 32 bits registers (if your processor is 386 or newer). The routine can be rewriten to:
Code: [Select]
  cmp al,11
  ja  .doNothing
  and eax,0xf
  jmp far [cs:eax*4+jmptable]
.doNothing:
« Last Edit: January 12, 2021, 12:27:21 AM by fredericopissarra »