Analysing Jump Tables in MSP430 Assembly Code

Jump Table

A jump table is an array of pointers to functions or an array of assembly code jump instructions. 

In assembling, jump tables are the most efficient method to handle switch statements with a large number of cases. The jump table is created only once and the required field in the table can be accessed simply by indexing.

Especially in embedded systems, where there is a heavy constraint in available memory, jump tables can be efficient while consuming lesser memory too.

Sample Program

Fig 1. Sample Program

The switch has only four cases, hence there is no need for a jump table. The cases are implemented simply as:

Fig 2. The switch implementation without jump table

The behavior is almost as expected.

Now, I need a switch with enough cases, to get the attention of the gcc compiler heuristics.

Fig 3. More cases for the switch

I have to check the corresponding assembly code generated for the above program, to be sure.

Fig 4. Lookup table created - PartI

Fig 5. Lookup table created - PartII

 It worked, the compiler decided that a jump table is really essential now.

The "mov #1,@r4" line stores the value of variable "i". There are 8 cases, numbered from 0 to 7. Hence first "i", i.e, @r4 is compared with 8, for obvious reasons.

Analysing the 'jump table'

The jump table has been created, starting from the address denoted by the label ".L11".

The first entry in the table holds label ".L3" which is the starting address  of the block of statements under "case 0:".
The next entry is ".L4", which is the starting address of the block of statements under "case 1:".
And so on ... Till "case 7:".
There are 8 ".word"s in the jump table too. Correct!

The line N in the jump table holds the starting address of the block of statements under the corresponding "case N:". In other words, each line is the offset to be added to ".L11", to execute the required case statements.

Decoding ...

"r15" holds the value to be switched.

"rla r15" rotates left arithmetically the value inside r15, once (multiplication by 2).
Remember that even addressing is required for MSP430 family.

"add #.L11,r15" adds the present value of "r15" (similar to offset), with the address of the  label ".L11" (similar to base address).
"r15" now contains the address of the line that lies at the given offset from ".L11".

After the "mov @r15,r15" line, "r15" now contains the starting address of a block of statements under the selected "case".

"br r15" simply branches to the address pointed to by r15.

Clean.

Issues

• How can you justify that jump tables are friendly to embedded systems?

Its true that a jump table has a particular overhead for itself.

Suppose there are a very large number of switch cases. Then, this "jump to index" overhead will be much lower than the cost to perform N case comparisons. That is why jump tables are usually preferred.

• Jump tables work only when the case identifiers are consecutive.

For example, case 1, case 2, case 3, etc ...

In situations where the cases are random and spread over a large range, suitable searching methods are needed. Normally, binary search is used. The correct case can then be selected in 3 or 4 steps without performing N comparisons each time.

Assembling in MSP430G2231

Sample Program

mov #0x0260,r5
mov #0x0270,r6

    Loop:
cmp #0,@r5
jz End
mov @r5,@r6
incd r5
incd r6
jmp Loop

    End:
mov #0x01,&0x22
mov #0x01,&0x21

This code demonstrates a simple implementation of 'strcpy' in msp430 assembly code. The first string is present in the location 0x0260. It is to be copied to another memory location starting from 0x0270. The RAM area of MSP430G2231 lies in the range 0x0200 to 0x027F.

Whats worth noticing is the ease with which some operations are defined which are otherwise very difficult in other assembly codes.

The program exits gracefully by lighting the red led, after successfully copying the string.

Notations

# - This symbol is used to indicate a pure number. The
      number can be an integer, in binary or a
      hexadecimal.
      For example, "mov #0x0260,r5" will move the hex
      number 0260 to register r5.

@ - It can happen that, the data stored in a register is
      the address of another memory location. The actual
      value inside this address can be accessed by using
      the '@' symbol. When '@' is used, the value in a
      register is interpreted to be the address of a memory
      location, and the actual data present in this location
      is fetched.
      The line "cmp #0,@r5" compares the number 0 with
      the data in the memory location pointed to by the
      value of r5.

& - When the address of a location is to be used directly,
      the '&' symbol is used. If not, the address is
      interpreted as just a number, thereby generating errors.

Notable Feature

@ and again @
    The line "mov @r5,@r6" is simple, sleek, easy-to-understand, self explanatory and normally illegal in other assembly languages.

    Technically, the '@' operation is emulated for the destination part. The "mov @r5,@r6" line will be changed to "mov @r5,0x0(r6)" after running msp430-gcc.

Conclusion

The MSP-EXP430G2 Launchpad (TI) for the MSP430 family

Altogether, there are only 27 instructions with about 7 addressing modes in the MSP430 family, which are easy to grasp and employ.
  
Coding in MSP430 family is fun!