Homework 7

22C:18, Spring 1996

Due Tuesday Mar. 12, 1996 in discussion

1. Consider the following data structure: HT is a statically allocated table in the data segment where each entry is a record with 2 fields, SYM and VAL. The SYM field of each record holds a string of ASCII characters, with unused characters set to NULL. The VAL field is a longword integer. The assembly time constant STRLEN gives the length of the string fields, and the assembly time constant HTSIZE gives the size of the table.

   Write appropriate assembly code (DS, DC, and EQU directives, plus appropriate comments) to define this data structure.

2. Write assembly code for a procedure called INIT that initializes the table HT so that all the SYM fields contain strings of STRLEN NULL characters and so that all VAL fields are set to $80000000.

3. Write assembly code for a function called HASH(S,L). The parameter S, passed by value, is a pointer to the first character of a string. The parameter L, passed by value, is the length of the string, in bytes. Hash uses the table HT and does a hashed lookup for the table entry containing the string S.

   If S is already in HT, HASH returns a pointer to the corresponding VAL field.

   If S is not in HT, HASH puts it in HT and returns a pointer to the corresponding VAL field.

   If S is not in HT and HT is full, HASH returns a null pointer.

   The hash function used should be something like the sum of the ASCII values of the significant bytes in the string, perhaps multiplying by 5 before adding each successive new byte to the sum. Collision resolution should be by linear search.

4. Write a program for the calculator used in the current machine problem that will compute and print the Fibonacci series up to 1000, terminating when the first number larger than 1000 is found. Each member of the Fibonacci series is the sum of the two previous members, as follows:

         0 1 1 2 3 5 8 13 ....