## Jump tables in GAS

21 posts / 0 new
Author
Message

This is probably a dumb question.  That's a good start, isn't it? ;-)

I want to create a jump table, so I started with:

jump_table:
.byte pm_lo8(label1)
.byte pm_lo8(label2)
.byte pm_lo8(label3)
.
.
.

That resulted in multiple:

Error: junk at end of line, first unrecognized character is ('

Huh.  OK:

jump_table:
.byte lo8(pm(label1))
.byte lo8(pm(label2))
.byte lo8(pm(label3))
.
.
.

Same errors.

Yes, I know my table lacks the high-byte of each label.  That's intentional.  The high byte of each will be the same, as each label will be in the same 256-word flash page, so I'll load ZH with an ldi and save some space in flash.

Some Googlin', and I found this unsatisfying conclusion:

https://lists.nongnu.org/archive/html/avr-gcc-list/2008-01/msg00169.html

I am wondering why something like this works:
ldi r31, lo8(gs(foo))

and this not:
.byte lo8(gs(foo))


Why does as or ld (?) in the latter state it's not constant and the second is no problem?

After some more testing I found out that constructions like:

.byte lo8(1024)

are not allowed.

Is this a bug?


This is from the last post in that thread.

A bit more noodling on my end, and I can guess that binutils was ust never meant to handle only part of a program memory address.

This works:

	.byte lo8(label1)

... as does this:

	.word pm(label1)

... but of course neither of those things gets me what I want:  a jump table comprised of only the LSB of a number of program addresses suitable for use with ijmp.

My Googlin' Fu seems not up to the task of discovering how exactly I should be doing this, or if it is even possible with gas.  The avr-gcc-list thread linked above makes some noises about building with dummy values, analysing the map file, injecting corrected addresses in place of the dummies, and building (or just linking again).  This is equally unsatisfying.

Any guidance is appreciated.  Suggestions that I abandon gas and switch to  avrasm2 are unwelcome :-)

This topic has a solution.
 "Experience is what enables you to recognise a mistake the second time you make it." "Good judgement comes from experience.  Experience comes from bad judgement." "Wisdom is always wont to arrive late, and to be a little approximate on first possession." "When you hear hoofbeats, think horses, not unicorns." "Fast.  Cheap.  Good.  Pick two." "We see a lot of arses on handlebars around here." - [J Ekdahl]

Last Edited: Fri. Nov 27, 2020 - 02:51 PM

This is probably a dumb question.

Dumb answer: Try putting .byte at the start of the line without tabs or spaces??

John Samperi

Ampertronics Pty. Ltd.

www.ampertronics.com.au

* Electronic Design * Custom Products * Contract Assembly

js wrote:
Dumb answer: Try putting .byte at the start of the line without tabs or spaces??
Can't hurt to try!

Error: junk at end of line, first unrecognized character is ('

Can't help, either, apparently :(

 "Experience is what enables you to recognise a mistake the second time you make it." "Good judgement comes from experience.  Experience comes from bad judgement." "Wisdom is always wont to arrive late, and to be a little approximate on first possession." "When you hear hoofbeats, think horses, not unicorns." "Fast.  Cheap.  Good.  Pick two." "We see a lot of arses on handlebars around here." - [J Ekdahl]

This works for avrasm2:

.db low(label1), low(label2), low(label3), low(label4)

; or:

.db low(label1), low(label2)
.db low(label3), low(label4)


Should work accordingly for GAS, I guess.

s'AVR wrote:
Should work accordingly for GAS, I guess.
Guess again - the opcodes may be the same (except even those are not 100% exact!) but the directives/operators etc are entirely different between avrams2 and avr-as

I tried ideas to get round what Joey found but hit the same wall. Wonder if it one could force the C compiler to generate a .s to show how to do it?

clawson wrote:
force the C compiler to generate a .s to show how to do it?

+1

Top Tips:

1. How to properly post source code - see: https://www.avrfreaks.net/comment... - also how to properly include images/pictures
2. "Garbage" characters on a serial terminal are (almost?) invariably due to wrong baud rate - see: https://learn.sparkfun.com/tutorials/serial-communication
3. Wrong baud rate is usually due to not running at the speed you thought; check by blinking a LED to see if you get the speed you expected
4. Difference between a crystal, and a crystal oscillatorhttps://www.avrfreaks.net/comment...
5. When your question is resolved, mark the solution: https://www.avrfreaks.net/comment...
6. Beginner's "Getting Started" tips: https://www.avrfreaks.net/comment...

clawson wrote:
Wonder if it one could force the C compiler to generate a .s to show how to do it?
I started a thought experiment on that before starting the thread.  'For deity's sake, the compiler generates jump tables for breakfast.  Surely gas can handle this...'  But the twist is that the compiler will, I suspect, always generate jump tables with complete entries, and as my OP demonstrates, .byte .word has no issue with a simple pm(label).  I'm trying to omit the MSB and use .byte.

Further, the avr-gcc-list thread I linked to seems to suggest the problem lies with binutils, not with avr-gcc.  But that may certainly be an incorrect analysis.  EDIT:  indeed, the error messages themselves appear to be issued by the assembler. /EDIT

I shall have to try to coerce the C compiler into chasing after a ball I faked throwing, and see where it runs... I just don't yet quite know how to do that.  I'll give it some thought, though.

 "Experience is what enables you to recognise a mistake the second time you make it." "Good judgement comes from experience.  Experience comes from bad judgement." "Wisdom is always wont to arrive late, and to be a little approximate on first possession." "When you hear hoofbeats, think horses, not unicorns." "Fast.  Cheap.  Good.  Pick two." "We see a lot of arses on handlebars around here." - [J Ekdahl]

Last Edited: Tue. Nov 24, 2020 - 04:24 PM

These relocs are not supported by gas. You have to take a different approach, e.g. the code as emit by avr-gcc (or extend gas to support it).

avrfreaks does not support Opera. Profile inactive.

SprinterSB wrote:
These relocs are not supported by gas
But... they are?:

https://sourceware.org/binutils/docs/as/AVR_002dModifiers.html

9.5.2.3 Relocatable Expression Modifiers

The assembler supports several modifiers when using relocatable addresses in AVR instruction operands. The general syntax is the following:

modifier(relocatable-expression)


pm_lo8

pm_lo8

This modifier allows you to use bits 0 through 7 of an address expression as an 8 bit relocatable expression. This modifier is useful for addressing data or code from Flash/Program memory by two-byte words. The use of ‘pm_lo8’ is similar to ‘lo8’.

pm_hi8

This modifier allows you to use bits 8 through 15 of an address expression as an 8 bit relocatable expression. This modifier is useful for addressing data or code from Flash/Program memory by two-byte words.

For example, when setting the AVR ‘Z’ register with the ‘ldi’ instruction for subsequent use by the ‘ijmp’ instruction:

ldi r30, pm_lo8(sym)
ldi r31, pm_hi8(sym)
ijmp


There seems to be no issue with using them in operands of instruction operands, only with pseudo ops like .byte.  So the machinery to handle the reloc is already in there.

I suspect I've misunderstood your meaning.

SprinterSB wrote:
You have to take a different approach, e.g. the code as emit by avr-gcc
I haven't yet sussed out how to coax avr-gcc to emit a jump table consisting of only the LSB of the addresses.

SprinterSB wrote:
or extend gas to support it
The thought crossed my mind, but composing an OP with a plea for help seemed like an easier first step :-)

 "Experience is what enables you to recognise a mistake the second time you make it." "Good judgement comes from experience.  Experience comes from bad judgement." "Wisdom is always wont to arrive late, and to be a little approximate on first possession." "When you hear hoofbeats, think horses, not unicorns." "Fast.  Cheap.  Good.  Pick two." "We see a lot of arses on handlebars around here." - [J Ekdahl]

Last Edited: Tue. Nov 24, 2020 - 03:10 PM

SprinterSB wrote:
extend gas to support it
A quick look at source shows that the pm_*8() relocs are >>specifically<< for use with ldi.  At the moment I wouldn't know where to begin to generalise their use to other instructions, or pseudo ops.

I found:

https://lists.nongnu.org/archive/html/avr-gcc-list/2010-05/msg00028.html

The pm operator works at the linker level, so it can accept
relocatable symbols (where the actual address is inserted by the
linker after resolving the relocation).

... which is expected.  It also possibly goes part of the way to explain why attempts like:

	.byte lo8(label1)/2


... and:

	.byte lo8(label1)>>1


... result in:

Error: junk at end of line, first unrecognized character is /'

... and:

Error: junk at end of line, first unrecognized character is >'

Basically, the expression accepted by the .byte pseudo op must be known before linking.

However, if that were the case, it would seem to me that neither of these should work:

	.byte lo8(label1)
	.word pm(label1)

... but they do.  That is, both .byte and .word are quite happy to take an operand which is unknown until link time.

What can be special about the use of pm_* (or combinations of pm with lo8/hi8/hh8) when used with .byte, which are simultaneously not special when used with .word?

EDIT:  Well, my link above goes on:

That's also
the reason why you cannot perform the bit shift directly in assembly
language: neither the ELF file format nor the GNU linker has any
method to transfer that bit shifting into the linker, as there is no
support for performing arbitrary arithmetics on relocational symbols.

(my emphasis)

 "Experience is what enables you to recognise a mistake the second time you make it." "Good judgement comes from experience.  Experience comes from bad judgement." "Wisdom is always wont to arrive late, and to be a little approximate on first possession." "When you hear hoofbeats, think horses, not unicorns." "Fast.  Cheap.  Good.  Pick two." "We see a lot of arses on handlebars around here." - [J Ekdahl]

Last Edited: Tue. Nov 24, 2020 - 04:37 PM

Also tried:

	.byte pm(label1)

... in the hopes that .byte would silently drop the high 8 bits, but:

Error: junk at end of line, first unrecognized character is ('

I can't catch a break :‑/

EDIT:

assembles:

------
.byte lo8()

.word pm()

doesn't:

--------

.word pm_lo8()

.word lo8() <--- this one is especially surprising!

.byte pm()

.byte pm_lo8() <--- this is really what I need...

 "Experience is what enables you to recognise a mistake the second time you make it." "Good judgement comes from experience.  Experience comes from bad judgement." "Wisdom is always wont to arrive late, and to be a little approximate on first possession." "When you hear hoofbeats, think horses, not unicorns." "Fast.  Cheap.  Good.  Pick two." "We see a lot of arses on handlebars around here." - [J Ekdahl]

Last Edited: Tue. Nov 24, 2020 - 04:30 PM

Also this:

... arrives at a similarly unsatisfactory (and ugly) solution.

An earlier dead end right here on AVR Freaks:

https://www.avrfreaks.net/forum/illegal-relocation-size

 "Experience is what enables you to recognise a mistake the second time you make it." "Good judgement comes from experience.  Experience comes from bad judgement." "Wisdom is always wont to arrive late, and to be a little approximate on first possession." "When you hear hoofbeats, think horses, not unicorns." "Fast.  Cheap.  Good.  Pick two." "We see a lot of arses on handlebars around here." - [J Ekdahl]

Last Edited: Tue. Nov 24, 2020 - 05:19 PM

	.text

label0:	nop
label1:	nop
label2:	nop

jumptab:
.byte label1-label0
.byte label2-label0


MattRW wrote:

Interesting idea.  However, that doesn't solve the underlying issue when implementing jump tables in gas for AVR.  GNU tools treat all address spaces as byte-oriented, whereas the hardware (via ijmp and the like) expects 16-bit-word addresses.  This can be seen in the values of the expressions that end up at the .byte locations:

Disassembly of section .text:

00000000 <label1>:
0:	00 00       	nop

00000002 <label2>:
2:	00 00       	nop

00000004 <label3>:
4:	00 00       	nop

00000006 <jumptab>:
6:	02 04                                               ..

HOWEVER!

label1:	nop
label2:	nop
label3:	nop

.type	jumptab, STT_OBJECT
jumptab:
.byte (label2-label1)/2
.byte (label3-label1)/2

... gets me:

Disassembly of section .text:

00000000 <label1>:
0:	00 00       	nop

00000002 <label2>:
2:	00 00       	nop

00000004 <label3>:
4:	00 00       	nop

00000006 <jumptab>:
6:	01 02                                               ..

So it seems that somewhat-more-arbitrary arithmetic is supported in the .byte pseudo op, as long as pm(), lo8(), etc. are not involved.  A bit more noodling and it seems that as long as the results of the expression will fit into 8 bits, it assembles as expected.

But I can't, for example:

	.byte (label1 / 2) & 0xFF
.byte (label2 / 2) & 0xFF
.byte (label3 / 2) & 0xFF


So, that gets me pretty far towards my goal, but since the jump table is a list of deltas from a root label, I have to fix it up afterwards, which turns out to fall prey to the original problem:

	ldi	ZH, hi8(jump_table + __AVR_PM_BASE_ADDRESS__)
add	ZL, r16	; r16 contains a mode number controlling the label to which to jump
ld	ZL, Z
subi	ZL, -lo8(pm(label1))
ijmp


The subi causes unhappiness:

Error: garbage at end of line
Error: can't resolve 0' {.text section} - lo8' {*UND* section}
Error: expression too complex


Curiously, it's the '-' which seems to push it over the edge, because it assembles without it.  So I would need an 'addi' instruction :-/

I can use another register:

	ldi	ZH, hi8(jump_table + __AVR_PM_BASE_ADDRESS__)
add	ZL, r16	; r16 contains a mode number controlling the label to which to jump
ld	ZL, Z
ldi	r17, lo8(pm(label1))
ijmp


... which would seem to work exactly as i would like it to, but the trouble is that it costs me those two extra instruction words, which incidentally exactly nullifies the savings I would make over a non-jump-table solution (for the app in question).

So not such a magnificent bastard after all ;-)

EDIT: typos

 "Experience is what enables you to recognise a mistake the second time you make it." "Good judgement comes from experience.  Experience comes from bad judgement." "Wisdom is always wont to arrive late, and to be a little approximate on first possession." "When you hear hoofbeats, think horses, not unicorns." "Fast.  Cheap.  Good.  Pick two." "We see a lot of arses on handlebars around here." - [J Ekdahl]

Last Edited: Tue. Nov 24, 2020 - 10:01 PM

Here is something ugly:

Put your jump table in its own section.

Use avr-nm to discover the desired values.

Generate a .c or .s file using those value for your jump table.

The result should contain only your jump table in its section.

Use avr-objcopy to remove the bad jump table and insert the good one.

Getting the good jump table at the same address

as the bad one is left as an exercise for the reader.

I did say it was ugly, but it can be automated.

Iluvatar is the better part of Valar.

Labels in the gnu assembler are of course "relocatable symbols", so after assembly they exist in the .o file as some sort of "magic thing" that the linker can do some simple math (addition and subtraction, probably) after the code has been moved to its final memory positions.    That "simple math" does not seem to include lo8()-like operations.  :-(

Matt's idea works since the difference between two relocatable symbols in the same section is an absolute number.

I like Skeeve's idea too...

This reply has been marked as the solution.

westfw wrote:

Matt's idea works since the difference between two relocatable symbols in the same section is an absolute number.

That was the key insight!

Here is a test program:

.equ	mode, 16

.section .vectors

.org 0

zero:
ldi	mode, -1

again:
inc	mode
andi	mode, 0x07

ld	ZL, Z
ijmp

label1:
rjmp	again

label2:
rjmp	again

label3:
rjmp	again

label4:
rjmp	again

label5:
rjmp	again

label6:
rjmp	again

label7:
rjmp	again

label8:
rjmp	again

.type	jump_table, STT_OBJECT
jump_table:
.byte ((label1 - zero) / 2) & 0xFF
.byte ((label2 - zero) / 2) & 0xFF
.byte ((label3 - zero) / 2) & 0xFF
.byte ((label4 - zero) / 2) & 0xFF
.byte ((label5 - zero) / 2) & 0xFF
.byte ((label6 - zero) / 2) & 0xFF
.byte ((label7 - zero) / 2) & 0xFF
.byte ((label8 - zero) / 2) & 0xFF


Assembled:

Disassembly of section .text:

00000000 <zero>:
0:	0f ef       	ldi	r16, 0xFF	; 255

00000002 <again>:
2:	03 95       	inc	r16
4:	07 70       	andi	r16, 0x07	; 7
6:	f0 e4       	ldi	r31, 0x40	; 64
8:	e0 e2       	ldi	r30, 0x20	; 32
a:	e0 0f       	add	r30, r16
c:	e0 81       	ld	r30, Z
e:	09 94       	ijmp

00000010 <label1>:
10:	f8 cf       	rjmp	.-16     	; 0x2 <again>

00000012 <label2>:
12:	f7 cf       	rjmp	.-18     	; 0x2 <again>

00000014 <label3>:
14:	f6 cf       	rjmp	.-20     	; 0x2 <again>

00000016 <label4>:
16:	f5 cf       	rjmp	.-22     	; 0x2 <again>

00000018 <label5>:
18:	f4 cf       	rjmp	.-24     	; 0x2 <again>

0000001a <label6>:
1a:	f3 cf       	rjmp	.-26     	; 0x2 <again>

0000001c <label7>:
1c:	f2 cf       	rjmp	.-28     	; 0x2 <again>

0000001e <label8>:
1e:	f1 cf       	rjmp	.-30     	; 0x2 <again>

00000020 <jump_table>:
20:	08 09 0a 0b 0c 0d 0e 0f                             ........

It's still a bit of a kludge.  A macro makes it a bit less ugly:

.macro jmptab label
.byte	((\label - zero) / 2) & 0xFF
.endm
.
.
.
.type	jump_table, STT_OBJECT
jump_table:
jmptab	label1
jmptab	label2
jmptab	label3
jmptab	label4
jmptab	label5
jmptab	label6
jmptab	label7
jmptab	label8
`

I can only mark one post as the solution, but both Matt and Bill share in the kudos.  Thanks to skeeve also for an alternative ugliness to the ugliness suggested in the avr-gcc-list thread.  Indeed, thanks to all respondents.

EDIT:  cleanup

 "Experience is what enables you to recognise a mistake the second time you make it." "Good judgement comes from experience.  Experience comes from bad judgement." "Wisdom is always wont to arrive late, and to be a little approximate on first possession." "When you hear hoofbeats, think horses, not unicorns." "Fast.  Cheap.  Good.  Pick two." "We see a lot of arses on handlebars around here." - [J Ekdahl]

Last Edited: Wed. Nov 25, 2020 - 05:01 PM

You do not need to have your your jump table and targets in the .vectors section.

'Tis sufficient that you know the least 8 bits of the "zero" symbol.

Possibly wasting some space with .align would do the trick.

Also, you could use a linker option to force the location of the section.

Also, you could link twice a la my previous suggestion.

This time would be simpler: the only difference between

the first and second links would be a symbol definition.

Iluvatar is the better part of Valar.

skeeve wrote:

You do not need to have your your jump table and targets in the .vectors section.

Understood.  My test code was adapted from an existing application.  I typically use .section .vectors along with -nostartfiles to ensure code starts at 0x0000.

 "Experience is what enables you to recognise a mistake the second time you make it." "Good judgement comes from experience.  Experience comes from bad judgement." "Wisdom is always wont to arrive late, and to be a little approximate on first possession." "When you hear hoofbeats, think horses, not unicorns." "Fast.  Cheap.  Good.  Pick two." "We see a lot of arses on handlebars around here." - [J Ekdahl]

Just for my own satisfaction, and possibly the future avoidance of confusion - what you have generated here isn't strictly a jump table, right? It's neither a list of addresses nor a list of jump instructions, but is instead a list of low bytes of target addresses... you still need to do some work to to generate the actual target address?

I'm reminded of a state machine I built a few years back initially consisting of a large array of entries each along the lines of {next_state, *action} - the table was the depth of the number of states (a lot!) and the width of the number of events that could change state (also a lot) and as this was a 32-bit arm system each entry was a 32-bit default enum and a 32-bit function pointer. It took, from memory, on the order of 40k of memory to hold it.

Obviously, that was an issue; I only had 92k to play with... first step was to use packed enums at 8 bits each, but things still got stuffed into 2 * 32 courtesy of the alignment. But replacing the action pointer with another packed enum, which referenced a single array of 32 bit pointers, did the trick, and reduced the size of the state array to a quarter of the original size.

Driving the state machine was simple: when an event occurs, the new state is table[current_state][event] and the desired action is at actions[table[current_state][event]]. Both state and action can be do-nothing, and in practical terms the actions were pointers to a list of atomic actions.

The huge huge bonus to this mechanism was that it could be automatically generated from an excel table; adding a new event or action was trivial, as was changing a particular state.

Neil

barnacle wrote:

Just for my own satisfaction, and possibly the future avoidance of confusion - what you have generated here isn't strictly a jump table, right? It's neither a list of addresses nor a list of jump instructions, but is instead a list of low bytes of target addresses... you still need to do some work to to generate the actual target address?

There appear to be a broad range of accepted definitions, e.g.:

https://stackoverflow.com/questions/48017/what-is-a-jump-table

A jump table can be either an array of pointers to functions or an array of machine code jump instructions.

https://en.wikipedia.org/wiki/Jump_table

Branch table

(Redirected from Jump table)

In computer programming, a branch table or jump table is a method of transferring program control (branching) to another part of a program (or a different program that may have been dynamically loaded) using a table of branch or jump instructions. It is a form of multiway branch.

Another method of implementing a branch table is with an array of pointers from which the required function's address is retrieved. This method is also more recently known under such different names as "dispatch table" or "virtual method table" but essentially performing exactly the same purpose. This pointer function method can result in saving one machine instruction, and avoids the indirect jump (to one of the branch instructions).

The resulting list of pointers to functions is almost identical to direct threaded code, and is conceptually similar to a control table.

The actual method used to implement a branch table is usually based on:

• the architecture of the processor on which the code is to be executed,
• whether it is a compiled or interpreted language and
• whether late binding is involved or not.

So while jump table is acceptable, it's perhaps more properly called a dispatch table.  More generally, a control table.

EDIT to add:  While storing only the LSB of an address is perhaps an uncommon approach, it is still an address.  It's just that it's an address constrained to within a single page.  The work to be done is the same: index the table, look up the address at that index, and jump to that address.  The only additional work is to specify the MSB of the address.  This does not, I think, disqualify consideration of this approach as a jump table, dispatch table, or control table. /EDIT

barnacle wrote:

The huge huge bonus to this mechanism was that it could be automatically generated from an excel table; adding a new event or action was trivial, as was changing a particular state.

Clever!

 "Experience is what enables you to recognise a mistake the second time you make it." "Good judgement comes from experience.  Experience comes from bad judgement." "Wisdom is always wont to arrive late, and to be a little approximate on first possession." "When you hear hoofbeats, think horses, not unicorns." "Fast.  Cheap.  Good.  Pick two." "We see a lot of arses on handlebars around here." - [J Ekdahl]

Last Edited: Sun. Nov 29, 2020 - 03:57 AM