## Dispatch tables...

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

### Dispatch tables...

(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...

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.

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

### Re: Dispatch tables...

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...

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.

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

### Re: Dispatch tables...

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
84 36
85 82
87 12
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 <..>

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

### Re: Dispatch tables...

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

; R0=noncontiguous index
MOV R2,#0
.loop
LDRB R3,[R1,R2]
TST R3
BEQ nomatch
CMP R0,R3
BNE loop
LDR PC,[PC,R2]
EQUD 0 ; pipeline
.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