Hi. I need help with my lab.
CIS 216 – Computer Organization Lab 08 – Jump Tables Fortune Teller 1 Introduction – Case/Switch Statements Very often in programming, we have to make one choice from a set of mutually exclusive options. This can be done with a series of if...else if... statements, but a nicer way is to use a switch/case statement. Here’s an example: Suppose we have a database of user data that includes birthdays. When birthday information is accessed, we wish to print out the name of the months (“January”, “February”,… etc.) instead of the numeric value 1-12 stored in the database. One way to do this is with a long if…else structure as shown in Figure 1. Another way is to use the case/switch structure shown in Figure 2. While both solutions yield the desired result, there are significant differences between the 2. For one thing, case/switch statement tend to be easier to read and therefore to maintain. (In this particular example, because we have a single line of code for each case, our if-then structure doesn’t contain the 12 sets of matched braces as we would normally have, making the readability advantage of the case structure less obvious). But the true advantage of the case structure has to do with efficiency and execution speed. Whereas the if-then structure is based on computationally expensive comparisons, the case structure is often purely computational, meaning that it can be to implemented without performing any comparisons! For the if-then structure, the time it takes to execute depends on the value of month. If month is 12, for example, then all 12 comparisons have to be carried out before the correct match is found. This is not true for our case structure. It executes quickly no matter what the value of month happens to be. So, how is it that the case statement in this example is able to execute so efficiently and without doing any comparisons? This has to do with how case statements are implemented. Unlike if-then statements, case statements can often be implemented with jump tables. JVolcy – Spelman College – Computer and Information Sciences 1 2 Jump Tables A jump table is an array of words containing addresses that correspond to labels in assembly code. The labels can refer to memory locations in the code segment, in which case the jump table is a list of addresses to which we can jump. Or, the labels can refer to memory locations in the data segment, in which case the jump table is a list of data storage locations. Consider the MIPS code shown in Figure 3. This code is the assembly implementation of the case statement shown in Figure 2. In the data segment, we reserved space for the 12 strings “January” to “December” (lines 22-33). To each string, we’ve assigned a label str1 - str12. These labels are the location of each string in memory. Next, we reserve 12 32-bit words in the data segment beginning at the label jump_table (line 36) JVolcy – Spelman College – Computer and Information Sciences 2 Figure 3. MIPS implementation of a switch/case statement for printing out the months of the year. JVolcy – Spelman College – Computer and Information Sciences 3 The 12 words are initialized with the addresses of the 12 month strings. Thus, symbolically, jump_table[0] points to the beginning of the “January” string, jump_table[1] points to the beginning of the “February” string, etc. So, to print the name of month 11 (which is December, in this 0-11 numbering scheme), one simply prints the string starting at jump_table[11]. No comparisons are required compared to an implementation based on the if-then code of Figure 1. Also, printing month 11 is equally fast as printing month 0. The text segment of Figure 3 contains code that first prompt the user for a number from 0 to 11 (lines 39-42) and reads in the user’s response into register $v0 (lines 44-46). The jump table is then indexed to the proper table entry (lines 49-51) in order to read in the address of the proper month name string (line 52). This string is then printed (lines 53-54). 3 Fortune Teller For this lab, you will be creating a fortune teller based on what we’ve learned about jump tables. The instructor will demonstrate the operations of a completed fortune teller that tells fortunes based on data provided by the user. The program works as follows: each fortune consists of 4 sentences, with a fixed grammatical structure. Therefore, it is easy to randomly replace any of the 4 sentences and still create a grammatically correct story. The 4 sentences have the following structure: Sentence 1: Creates a subject (person or thing) Sentence 2: Describes the subject Sentence 3: Predicts an action by the subject Sentence 4: Offers the user some advice An example fortune might read like this: Sentence 1: A congressman from Texas Sentence 2: Who speaks with a lisp Sentence 3: Wants to friend you on Facebook Sentence 4: Better run the other way! Note that it is easy to come up with alternate phrases for each of the 4 sentences. So, for example, sentence 1 can easily be replaced by one of these alternates: “A two-timing bodybuilder” “A millionaire musician” or “A Morehouse man” Likewise, sentence 2 can be easily replaced by one of these alternates: “Carrying a small dog” “With a wart on his nose” JVolcy – Spelman College – Computer and Information Sciences 4 or “Who doesn’t seem to own a comb” To keep matters simple, we will create only 4 alternates for each sentence. Prompt the user for information that can be used to select sentences used in building the fortune. For example, you can use the user’s age, today’s date, the user’s birthday, etc. Note that since we create 4 alternates for each sentence, we must deal with user values that can be greater than 4 (the best way to do this is to AND the user’s input with a 3 [binary 11]). Use the jump table example above to create 4 jump tables, one for each of the sentences in the fortune. Just as the jump table in the example allowed us to select one of 12 months, your