Dispatch tables...

Discuss all aspects of programming here. From 8-bit through to modern architectures.
Post Reply
alex_farlie
Posts: 142
Joined: Sun Jul 07, 2013 9:46 pm
Contact:

Dispatch tables...

Post by alex_farlie » Wed Aug 22, 2018 12:25 am

(This is under programming as it's essentially a question of how where they are or were implemented on Acorn/ RISC OS based platforms)

For the purposes of the discussion, a Dispatch table, is a list of paired values in memory, which give a list of addresses to call.

In a simple case, the entries would have an implied index, meaning that simple indexed addressing could be used.

However, when you don't have a continuous range of possible input values, this approach would use up memory allocating 'blank' or 'null' entries, a key, value approach would be used. How was key,value pair despatch handled on Acorn/RISC OS systems? I've seen two different approaches used in BBC micro ROM's for example...

Alex Farlie.
Last edited by alex_farlie on Fri Aug 24, 2018 9:34 am, edited 2 times in total.

Phlamethrower
Posts: 103
Joined: Fri Nov 24, 2017 1:35 pm
Contact:

Re: Dispatch tables...

Post by Phlamethrower » Wed Aug 22, 2018 11:02 pm

I haven't looked at the algorithms in any detail, but for current RISC OS versions:
  • SWIs number -> handler lookup is via a hash table (mapping to handlers for each SWI chunk), except for kernel SWIs which use a lookup table for each SWI number
  • Interrupt handlers and vector claimants use arrays (indexed by the IRQ number / vector number) which point to linked lists (actually, the head element of the linked list is the array element)
  • Service call handlers use an array of linked lists (for low-numbered handlers), and a hash table (for higher numbers). However even with this approach there's still the obvious inefficiency that the code always jumps to the main service call handler of the module, instead of directly to the handler for the specific service.
  • *Commands also use a hash table of some kind
Earlier OS versions were less efficient with how they did things, e.g. the hash-table based service call handling was only introduced in RISC OS 3.8. I'm not sure when the other hash tables were introduced.

User avatar
BigEd
Posts: 2527
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

Re: Dispatch tables...

Post by BigEd » Thu Aug 23, 2018 7:45 am

alex_farlie wrote:
Wed Aug 22, 2018 12:25 am
I've seen two different approaches used in BBC micro ROM's for example...
If you could sketch those and/or provide pointers to a disassembly, that would be great! It would then be worthwhile to try the question over on the programming forum at 6502.org. It's a good question!

alex_farlie
Posts: 142
Joined: Sun Jul 07, 2013 9:46 pm
Contact:

Re: Dispatch tables...

Post by alex_farlie » Thu Aug 23, 2018 3:22 pm

BigEd wrote:
Thu Aug 23, 2018 7:45 am
alex_farlie wrote:
Wed Aug 22, 2018 12:25 am
I've seen two different approaches used in BBC micro ROM's for example...
If you could sketch those and/or provide pointers to a disassembly, that would be great! It would then be worthwhile to try the question over on the programming forum at 6502.org. It's a good question!
I don't recall the exact techniques but one related to service calls... ( number, address) pairs, and the other to command pairs (star command table) IIRC.

I'll have another think about this when I can find the example again....

User avatar
MartinB
Posts: 5213
Joined: Mon Mar 31, 2008 9:04 pm
Location: Obscurity
Contact:

Re: Dispatch tables...

Post by MartinB » Thu Aug 23, 2018 4:12 pm

In my roms, I use a command table which blends the ASCII comand-line star command, the *HELP output ASCII string and the command absolute call address. At run-time, the rom command line parser steps along the incoming command comparing it with the command list where the end of each of the latter are marked by the first encountered <space>. If a command name match occurs, the indirect jump address is found by continuing along the rom command list string until the first negative byte is found where this and the subsequent byte form the big-endian indirect jump address within the rom. (We know the hi byte of any sideways rom command execution address will always be negative because sideways roms live at $8000 onwards.)

The text snips and dumps below show my I2C v2 rom construct as an example of the method I use.....

Code: Select all

\Command table as :	'*COMMAND <spc> *HELP dialogue'
\		 	 <command label>

comtab	ASC	'I2C'
	DFDB	stari2c
	ASC	'I2CRESET'
	DFDB	starrst
	ASC	'I2CQUERY (Q)'
	DFDB	i2cquery
	ASC	'I2CTXB <addr> (<#nn>) <byte>(;)'
	DFDB	i2ctxb
	ASC	'I2CTXD <addr> (<#nn>) <no.bytes>(;)'
	DFDB	i2ctxd
	ASC	'I2CRXB <addr> (<#nn>) (A%-Z%)'
	DFDB	i2crxb
	ASC	'I2CRXD <addr> (<#nn>) <no.bytes>'
	DFDB	i2crxd
	ASC	'I2CSTOP'
	DFDB	starstp

	DFB	$FF		\end of table marker


<..rom content snip showing mixed ASCII and hex..>
I2C
81 E3
I2CRESET
81 F3
I2CQUERY (Q)
82 CC
I2CTXB <addr> (<#nn>) <byte>(;)
84 36
I2CTXD <addr> (<#nn>) <no.bytes>(;)
85 82
I2CRXB <addr> (<#nn>) (A%-Z%)
87 12
I2CRXD <addr> (<#nn>) <no.bytes>
88 C6
I2CSTOP
82 81
FF
<..>

<..rom content snip showing actual hex bytes..>
49 32 43 81 E3 49 32 43
52 45 53 45 54 81 F3 49
32 43 51 55 45 52 59 20
28 51 29 82 CC 49 32 43
54 58 42 20 3C 61 64 64
72 3E 20 28 3C 23 6E 6E
3E 29 20 3C 62 79 74 65
3E 28 3B 29 84 36 49 32
43 54 58 44 20 3C 61 64
64 72 3E 20 28 3C 23 6E
6E 3E 29 20 3C 6E 6F 2E
62 79 74 65 73 3E 28 3B
29 85 82 49 32 43 52 58
42 20 3C 61 64 64 72 3E
20 28 3C 23 6E 6E 3E 29
20 28 41 25 2D 5A 25 29
87 12 49 32 43 52 58 44
20 3C 61 64 64 72 3E 20
28 3C 23 6E 6E 3E 29 20
3C 6E 6F 2E 62 79 74 65
73 3E 88 C6 49 32 43 53
54 4F 50 82 81 FF <..>

User avatar
jgharston
Posts: 3569
Joined: Thu Sep 24, 2009 11:22 am
Location: Whitby/Sheffield
Contact:

Re: Dispatch tables...

Post by jgharston » Thu Aug 23, 2018 8:37 pm

Something I've seen in ARM code is along the lines of:

; R0=noncontiguous index
ADR R1,match
MOV R2,#0
.loop
LDRB R3,[R1,R2]
TST R3
BEQ nomatch
CMP R0,R3
ADDNE R2,R2,#4
BNE loop
LDR PC,[PC,R2]
EQUD 0 ; pipeline
EQUD address3
EQUD address4
EQUD address17
EQUD address23
EQUD address67
.match
EQUB 3
EQUB 4
EQUB 17
EQUB 23
EQUB 67
EQUB 0
ALIGN

Untested, and probably full of syntax errors!

Code: Select all

$ bbcbasic
PDP11 BBC BASIC IV Version 0.25
(C) Copyright J.G.Harston 1989,2005-2015
>_

Post Reply