Home > Mobile >  Is it possible to have a switch/case with mips using a JumpTable for non sequential options?
Is it possible to have a switch/case with mips using a JumpTable for non sequential options?

Time:05-11

I want to practice using switch/cases and JumpTables in MIPS. Currently, I am able to achieve a similar logic via stacking several BEQ commands after each other. I'd prefer to switch it over to using a single switch statement with cases. Unfortunately, the cases are not in sequential order. There is a user-menu where they enter a character (ascii value) and based on that character, an action occurs. For example, they can choose 'A', 'D', 'N', 'X'. Obviously, that is not in order... I am considering to store an array with the options and treat it as an ENUM (which doesn't exist in MIPS as far as I'm aware) which would solve the non-sequential issue and have an easier time converting the case to the proper character.

This is a bit of my code as of now to help clear things up: Note that the issue is with the switch/jump rather than the actual logic/action performed in the cases

C Example:

//switch case sample based on char 
char ch;
cout << "Enter a character: ";
cin >> ch;
switch (ch)
{
case 'N':
    //action to perform
    cout << "N: " << endl;
    break;
case 'A':
    //action 
    cout << "A: " << endl;
    break;
default:
    cout << "You entered an invalid character" << endl;
    break;
}

and my current mips solution:

.data
 .asciiz 
 enterMenu: "Enter a menu option (N,A,M,D,X):\n"

.word 
JT: N,A,M,D,X #all the possible cases we want to deal with 
 .text 
la $a0, enterMenu #load meu prompt
li $v0, 4 #print prompt 
syscall 

li $v0, 12 #read char from user
syscall 

add $t0, $v0, $0 #move the character to a temporary register (holds switch value)

#switch (k) k = $s5
slti    $t3, $t0, 65    # Test if k < 65 (A's ascii value)
bne     $t3, $zero, Exit # if k < A, go to Exit

slti    $t3, $t0, 90    #Test if k > 90 (Z's ascii value)
beq $t3, $zero, Exit    # if k > Z, go to Exit


beq     $t0, 65, A  # if k = A, go to A
beq    $t0, 68 , D  # if k = D, go to D
beq    $t0, 77, M   # if k = M, go to M
beq    $t0, 78, N   # if k = N, go to n
beq    $t0, 88, X   # if k = X, go to X

Edit: The menu an probably be stored as follows:

 .byte 
  Cases: 'N','A','M','D','X' #added this in after

The question would then become on how to have them correspond (from the user input) to the JumpTable offset and then to picking cases.

CodePudding user response:

The series of beqs is as good as you're going to get for a small number of cases that are fairly spread out (e.g. A - X).


A data table of pointers to code would have to have 24 entries, many going to the default (no match) case.

Code sequence to use the table would:

  1. Normalize the input (e.g. subtract 'A'), 1 instruction (addiu)
  2. Check if greater than table size, 2 more instructions (sltiu / bnez for unsigned compare)
  3. Array index (shift, load address, add) 4 instructions on MARS (3 with an assembler with %hi(table) / %lo(table) to let you leave part of the table address for the lw immediate),
  4. Load the data pointer, 1 instruction
  5. Branch to data pointer in register, 1 instruction

For a total of 9 instructions (or 8) and a possible data cache miss, though an out of order machine would be able to parallelize execution of the 2 range-check instructions. (Or an in-order superscalar if you schedule them appropriately.)


The series of beq's for your set is 10 instructions (beq with a constant is a pseudo instruction that expands to first load the immediate, then compare & branch), though not all will always execute, and they can be ordered for performance. (Most common first.)

So, I would probably switch to the table version if there were more than 20 or so cases, since at 20 cases, on average, 10 instructions would execute (assuming equal distribution, better if you can order for known distribution.)

If the "default" case is most common, a range-check and/or a bitmap check like 0x12345 & (1<<c) could rule out being one of the special cases quickly, without going through them all.

  • Related