How do you do a Jump Table in the C backend?

Just starting out? Need help? Post your questions and find answers here.
User avatar
Demivec
Addict
Addict
Posts: 4086
Joined: Mon Jul 25, 2005 3:51 pm
Location: Utah, USA

How do you do a Jump Table in the C backend?

Post by Demivec »

I am familiar with jump tables and various options for doing them. I want to utilize labels within a procedure as jump points and have assembled their addresses within a DataSection within the procedure in question with a Label at the beginning.

How do I utilize an ASM jmp instruction to move to the desired jump address in the C backend? I know how to do this in the ASM backend.

I do not and honestly cannot use prototypes or other methods to accomplish what I need. I have contemplated various code structures to perform similar functions but none are up to the task.

I am specifically looking on a way to implement an jmp instruction by index into a table of addresses in the C backend. Any code that would generate the same result would be welcome. Hints are also welcome. :wink:

Here is the pseudo-code (missing the code). The variables index_1, index_2 & index_3 are global and are set outside the procedure to direct the flow within the procedure. Speed is a top priority as the procedure will be used as a callback and will be called many times.:

Code: Select all

Procedure x()
    ;how to replace the Goto with an ASM instruction to jmp to the indexed address in the C Backend?
    Goto ?jp_adr + (index_1 * SizeOf(Integer)) ;index_1 is an index into jump table.

    set_1a:
    ;code + next jump
    Goto ?jp_adr + (index_2 * SizeOf(Integer)) ;index_2 is an index into jump table.
    
    set_1b:
    ;code + next jump
    Goto ?jp_adr + (index_2 * SizeOf(Integer)) ;index_2 is an index into jump table.
    
    set_1c:
    ;code + next jump
    Goto ?jp_adr + (index_2 * SizeOf(Integer)) ;index_2 is an index into jump table.
    
    set_2a:
    ;code + next jump
    Goto ?jp_adr + (index_3 * SizeOf(Integer)) ;index_3 is an index into jump table.
    
    set_2b:
    ;code + next jump
    Goto ?jp_adr + (index_3 * SizeOf(Integer)) ;index_3 is an index into jump table.
    
    set_2c:
    ;code + next jump
    Goto ?jp_adr + (index_3 * SizeOf(Integer)) ;index_3 is an index into jump table.
    
    set_3a:
    ;code + next jump
    Goto exit
    
    set_3b:
    ;code + next jump
    Goto exit    
    
    set_3c:
    ;code 

    exit:
    procedureReturn
     
    DataSection
      jp_adr:
      Data.i ?set_1a, ?set_1b, ?set_1c, ?set_2a, ?set_2b, ?set_2c, ?set_3a, ?set_3b, ?set_3c
    EndDataSection
EndProcedure
jack
Addict
Addict
Posts: 1336
Joined: Fri Apr 25, 2003 11:10 pm

Re: How do you do a Jump Table in the C backend?

Post by jack »

hello Demivec :)
could you use an array of function pointers ? https://www.sanfoundry.com/c-tutorials-jump-tables/
User avatar
Demivec
Addict
Addict
Posts: 4086
Joined: Mon Jul 25, 2005 3:51 pm
Location: Utah, USA

Re: How do you do a Jump Table in the C backend?

Post by Demivec »

jack wrote: Tue Jun 28, 2022 12:12 am hello Demivec :)
could you use an array of function pointers ? https://www.sanfoundry.com/c-tutorials-jump-tables/
I don't think so. Thank you for your reply. I am aware of function pointers and prototypes as an option but i don't think they work well if at all.

If I am unable to replace the functionality of a simple Goto/Jump instruction I'll have to see what functionality I will have to sacrifice to get things to work within the limitations. I would rather being able to get identical results with each of the different backends. The C backend doesn't seem to be able to reproduce this same functionality as the ASM backend.
User avatar
idle
Always Here
Always Here
Posts: 5042
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: How do you do a Jump Table in the C backend?

Post by idle »

I won't have time to look at this until another 24 hours but it should be doable.
User avatar
idle
Always Here
Always Here
Posts: 5042
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: How do you do a Jump Table in the C backend?

Post by idle »

I think this should be ok, in the comments you can see the processed c and the processed asm in intel format

Code: Select all

;!//gccflags -masm=intel -S; 

Procedure foo(a.i)
  Protected result   
  !switch (v_a) {
  !case 1: 
  Goto l1; 
  !case 2: 
  result =2  
  Goto l2; 
  !case 3:
  Goto l3   
  !default: 
  Goto le 
  !}
  
  L1: 
  result = 1
  Goto Le
  L2: 
  result =2
  Goto le 
  l3: 
  result =3
  
  le:
  ProcedureReturn result  
  
EndProcedure   

foo(2)


; switch (v_a) {
; Case 1: 
; Goto ll_foo_l1;
; Case 2: 
; v_result=2;
; Goto ll_foo_l2;
; Case 3:
; Goto ll_foo_l3;
; Default: 
; Goto ll_foo_le;
; }
; ll_foo_l1:;
; v_result=1;
; Goto ll_foo_le;
; ll_foo_l2:;
; v_result=2;
; Goto ll_foo_le;
; ll_foo_l3:;
; v_result=3;
; ll_foo_le:;
; r=v_result;
; Goto End;
; r=0;
; End:
; Return r;
; }


; f_foo:
; 	push	rbp
; 	.seh_pushreg	rbp
; 	mov	rbp, rsp
; 	.seh_setframe	rbp, 0
; 	sub	rsp, 16
; 	.seh_stackalloc	16
; 	.seh_endprologue
; 	mov	QWORD PTR 16[rbp], rcx
; 	mov	QWORD PTR -8[rbp], 0
; 	mov	QWORD PTR -16[rbp], 0
; 	cmp	QWORD PTR 16[rbp], 2
; 	je	.L16
; 	cmp	QWORD PTR 16[rbp], 3
; 	je	.L26
; 	cmp	QWORD PTR 16[rbp], 1
; 	jne	.L27
; 	jmp	.L25
; .L16:
; 	mov	QWORD PTR -16[rbp], 2
; 	nop
; .L20:
; 	mov	QWORD PTR -16[rbp], 2
; 	jmp	.L22
; .L25:
; .L19:
; 	mov	QWORD PTR -16[rbp], 1
; 	jmp	.L22
; .L26:
; 	nop
; .L21:
; 	mov	QWORD PTR -16[rbp], 3
; 	jmp	.L22
; .L27:
; 	nop
; .L22:
; 	mov	rax, QWORD PTR -16[rbp]
; 	mov	QWORD PTR -8[rbp], rax
; 	nop
; .L23:
; 	mov	rax, QWORD PTR -8[rbp]
; 	add	rsp, 16
; 	pop	rbp
; 	ret

User avatar
STARGÅTE
Addict
Addict
Posts: 2067
Joined: Thu Jan 10, 2008 1:30 pm
Location: Germany, Glienicke
Contact:

Re: How do you do a Jump Table in the C backend?

Post by STARGÅTE »

But this code is not a jump table. It's a normal slow Select : Case structure.
Demivec is looking for an equivalent of:

Code: Select all

Procedure JumpTable(Index.i)
	
	! MOV  rdx, ll_jumptable_jumps
	! MOV  rax, [p.v_Index]
	! SHL  rax, 3
	! MOV  rax, [rax+rdx]
	! JMP  rax
	
	Pos0:
	Debug "Zero"
	ProcedureReturn
	Pos1:
	Debug "One"
	ProcedureReturn
	Pos2:
	Debug "Two"
	ProcedureReturn
	Pos3:
	Debug "Three"
	ProcedureReturn
	Pos4:
	Debug "Four"
	ProcedureReturn
	
	DataSection
		Jumps:
		Data.i ?Pos0, ?Pos1, ?Pos2, ?Pos3, ?Pos4
	EndDataSection
	
EndProcedure

JumpTable(2)
JumpTable(4)
However, I think this is not possible due to this C-backend limitation:
- No Label address in datasection (?Label)
PB 6.01 ― Win 10, 21H2 ― Ryzen 9 3900X, 32 GB ― NVIDIA GeForce RTX 3080 ― Vivaldi 6.0 ― www.unionbytes.de
Lizard - Script language for symbolic calculations and moreTypeface - Sprite-based font include/module
breeze4me
Enthusiast
Enthusiast
Posts: 511
Joined: Thu Mar 09, 2006 9:24 am
Location: S. Kor

Re: How do you do a Jump Table in the C backend?

Post by breeze4me »

Like this? (maybe GCC only)

Code: Select all

CompilerIf #PB_Compiler_Backend <> #PB_Backend_C
  End
CompilerEndIf


Procedure TestFunc(i)
  If i < 0 Or i > 6
    Debug "out of bounds"
    ProcedureReturn
  EndIf
  
  !integer *jt[] = {&&label_TestFunc_jmp0, &&label_TestFunc_jmp1, &&label_TestFunc_jmp2, &&label_TestFunc_jmp3, &&label_TestFunc_jmp4, &&label_TestFunc_jmp5, &&label_TestFunc_jmp6};
  
  !goto *jt[v_i];
  
  
  !label_TestFunc_jmp0:
  Debug 0
  !goto *jt[6];
  
  !label_TestFunc_jmp1:
  Debug 1
  !goto *jt[6];
  
  !label_TestFunc_jmp2:
  Debug 2
  !goto *jt[6];
  
  !label_TestFunc_jmp3:
  Debug 3
  !goto *jt[6];
  
  !label_TestFunc_jmp4:
  Debug 4
  !goto *jt[6];
  
  !label_TestFunc_jmp5:
  Debug 5
  
  
  !label_TestFunc_jmp6:
  Debug "exit"
  
EndProcedure


TestFunc(5)

User avatar
idle
Always Here
Always Here
Posts: 5042
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: How do you do a Jump Table in the C backend?

Post by idle »

breeze4me wrote: Wed Jun 29, 2022 10:41 am Like this? (maybe GCC only)


that's good I was under the impression that the optimizer would transform a switch to a jump table if you used constants but it's simply not the case I didn't have time to look

here's a combined method c and asm

Code: Select all

Procedure test(index)
    Protected result 
    
    CompilerIf #PB_Compiler_Backend = #PB_Backend_C   
    !integer *jt[] = { &&ll_test_l0 , &&ll_test_l1 , &&ll_test_l2 , &&ll_test_l3 , &&ll_test_l4};
    If index < 5
       !goto *jt[v_index];
    Else     
       Goto lE    
    EndIf 
    CompilerElse 
      DataSection : jt:
        Data.i ?l0 , ?l1 , ?l2 , ?l3 , ?l4
      EndDataSection 
      If index < 5 
        CompilerIf #PB_Compiler_Processor = #PB_Processor_x86
        !mov eax, [p.v_index] 
        !jmp dword [ll_test_jt] + eax * 4]
       CompilerElse
        !lea rdx, [ll_test_jt] 
        !mov rax,  [p.v_index] 
        !jmp qword [rdx + rax * 8]
      CompilerEndIf 
      Else 
       Goto Le 
      EndIf  
     
    CompilerEndIf 
    
    
    l0: 
    result =  0
    Goto lE 
    l1: 
    result = 1  
    Goto lE
    l2:
    result =  2  
    Goto lE 
    l3:
    result = 3 
    Goto lE 
    l4:
    result =  4  
    lE:
    
    ProcedureReturn result 
  EndProcedure    
  
  
  Debug test(0)
User avatar
idle
Always Here
Always Here
Posts: 5042
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: How do you do a Jump Table in the C backend?

Post by idle »

This is much better haven't tested on x86

Code: Select all

Procedure test(index)
  Protected result,addr 
  
  DataSection : jt:
    Data.i ?l0 , ?l1 , ?l2 , ?l3 , ?l4
  EndDataSection 
  
  If index < 5 
    
    addr = PeekI(?jt + (index* SizeOf(Integer)))
    CompilerIf #PB_Compiler_Backend = #PB_Backend_C    
      !goto *v_addr;  
    CompilerElse 
      EnableASM  
      jmp addr
      DisableASM 
    CompilerEndIf 
    
  Else 
    Goto le 
  EndIf  
  
  
  l0: 
  result =  0
  Goto lE 
  l1: 
  result = 1  
  Goto lE
  l2:
  result =  2  
  Goto lE 
  l3:
  result = 3 
  Goto lE 
  l4:
  result =  4  
  lE:
  
  ProcedureReturn result 
EndProcedure    


Debug test(3)
User avatar
STARGÅTE
Addict
Addict
Posts: 2067
Joined: Thu Jan 10, 2008 1:30 pm
Location: Germany, Glienicke
Contact:

Re: How do you do a Jump Table in the C backend?

Post by STARGÅTE »

hm, so you just ignore Fred's statement regarding the C-backend:
Fred wrote: Wed May 19, 2021 7:57 pm It only this syntax:

Code: Select all

Data.i ?Label
Which is not supported
Or is this now supported in the final 6.00 version?
PB 6.01 ― Win 10, 21H2 ― Ryzen 9 3900X, 32 GB ― NVIDIA GeForce RTX 3080 ― Vivaldi 6.0 ― www.unionbytes.de
Lizard - Script language for symbolic calculations and moreTypeface - Sprite-based font include/module
User avatar
idle
Always Here
Always Here
Posts: 5042
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: How do you do a Jump Table in the C backend?

Post by idle »

STARGÅTE wrote: Fri Jul 01, 2022 7:22 am hm, so you just ignore Fred's statement regarding the C-backend:
Fred wrote: Wed May 19, 2021 7:57 pm It only this syntax:

Code: Select all

Data.i ?Label
Which is not supported
Or is this now supported in the final 6.00 version?
Don't knock it, if it works. I was a little surprised, as I was also under the impression that it wasn't supported but that doesn't stop me trying.
Fred
Administrator
Administrator
Posts: 16619
Joined: Fri May 17, 2002 4:39 pm
Location: France
Contact:

Re: How do you do a Jump Table in the C backend?

Post by Fred »

STARGÅTE wrote: Fri Jul 01, 2022 7:22 am hm, so you just ignore Fred's statement regarding the C-backend:
Fred wrote: Wed May 19, 2021 7:57 pm It only this syntax:

Code: Select all

Data.i ?Label
Which is not supported
Or is this now supported in the final 6.00 version?

Yes it's supported in v6.00 final, sorry I forget to update it.
User avatar
useful
Enthusiast
Enthusiast
Posts: 367
Joined: Fri Jul 19, 2013 7:36 am

Re: How do you do a Jump Table in the C backend?

Post by useful »

We just need to update the basic features
goto label
gosub label
To
goto label/*pointer
gosub label/*pointer

In any case, the ![for c] / enable asm [for asm] option is now available.
Dawn will come inevitably.
User avatar
mk-soft
Always Here
Always Here
Posts: 5335
Joined: Fri May 12, 2006 6:51 pm
Location: Germany

Re: How do you do a Jump Table in the C backend?

Post by mk-soft »

Small optimation with ArrayOfPointer

Update
- Fix goto pointer

Code: Select all

Structure ArrayOfPointer
  *Index[0]
EndStructure

Procedure test(index)
  Protected *addr.ArrayOfPointer = ?jt 
  Protected result, *a
  
  DataSection : jt:
    Data.i ?l0 , ?l1 , ?l2 , ?l3 , ?l4
  EndDataSection 
  
  If index < 5 
    
    CompilerIf #PB_Compiler_Backend = #PB_Backend_C  
      !goto *(void*)p_addr->f_index[v_index];
    CompilerElse 
      EnableASM  
      jmp *addr\Index[index]
      DisableASM 
    CompilerEndIf 
    
  Else 
    Goto le 
  EndIf  
  
  
  l0: 
  result =  0
  Goto lE 
  l1: 
  result = 1  
  Goto lE
  l2:
  result =  2  
  Goto lE 
  l3:
  result = 3 
  Goto lE 
  l4:
  result =  4  
  lE:
  
  ProcedureReturn result 
EndProcedure    


Debug test(3)
Last edited by mk-soft on Sun Dec 10, 2023 7:02 pm, edited 1 time in total.
My Projects ThreadToGUI / OOP-BaseClass / EventDesigner V3
PB v3.30 / v5.75 - OS Mac Mini OSX 10.xx - VM Window Pro / Linux Ubuntu
Downloads on my Webspace / OneDrive
User avatar
idle
Always Here
Always Here
Posts: 5042
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: How do you do a Jump Table in the C backend?

Post by idle »

thanks, I was aiming for the minimization of inline asm and c but it's better without the peeki
Post Reply