Assignment 9, Solutions

Problems

1. Background: Consider the problem of designing a string package. Just to make it different from existing C or Java strings, we'll consider each string object to have a fixed size (so they can be statically allocated), but different string objects could have different sizes. Therefore, string objects have the following attributes:
   • s.size() -- the number of bytes occupied by the object.
   • s.capacity() -- the longest string the object could hold.
     Note, s.capacity() <= s.size(), always.
   • s.length() -- characters in the string the object currently holds.
     Note, s.length() <= s.capacity(), always.

   Appropriate operations on strings include (this is not an exhaustive list):

   • s.clear() -- initialize the string to empty.
   • s.get(i) -- if i<s.length() return the character i of the string; otherwise return NUL. Note that i=0 refers to the first character.
   • s.set(i,ch) -- if i<=s.length() set character i of the string; otherwise do nothing. Note, this may lengthen the string by 1, and if ch is NUL, it may shorten the string.
   • s.append(ch) -- append the character ch to the end of the string. This will lengthen the string by 1 except if ch is NUL or the s.length()=s.capacity().
   • s.trunc(i) -- truncate the string to i characters. Does nothing if i>s.length().
   • s.concat(s1) -- append as much of string s1 to string s as will fit.
   • s.copy(s1) -- copy as much of string s1 to string s as will fit. Equivalent to s.clear();s.concat(s1).

   a) Present a design for a representation of the string type. This problem does not ask for code, it asks for a design, that is, human-to-human communication before you start writing code. (0.5 points)

   Observations:
   a) Size is about the representation, length about the data.
   b) Capacity seems to be in between, none of them need be equal
   c) Clear obviously sets size to zero, but that's all.
   d) Each string could have a different size, capacity and length.
   e) The problem statement did not say null termination wat reqsuired.

   Solution:
   A string consists of a block of memory, size bytes.
   Word 1 of this block records the size.
   Word 2 of this block records the length.
   The characters of the string therefore begin at byte 8.
   After length characters, remaining bytes are undefined.
   Therefore, capacity = size - 8.

   b) Write a macro STRINGCONST such that
       A: STRINGCONST "string"
   will assemble a constant string object into memory. The handle for that object can be loaded into a register using LEA R,A or LIL R,A. Because it's a string constant, its capacity should, of course, be equal to its size. (0.5 points)

                   MACRO   STRINGCONST str
           qBEGINq =       .
           .       =       . + 8           ; reserve space for header
                   ASCII   str             ; fill in content
           qENDq   =       .               ; note the end of the string
           .       =       qBEGINq         ; go back to fill in header
           qSIZEq  =       qENDq - qBEGINq
                   W       qSIZEq          ; size field of header
                   W       qSIZEq - 8      ; length field equals capacity
           .       =       qENDq
                   ENDMAC
   

   Note: Labels of the form qXXq were used to distinguish symbols used in macro definitions from those used elsewhere. These are assumed to be temporary symbols that may be reused freely in macros. This convention is stolen from the hawk.macs file.

   c) Give appropriate content for the entry in the strings.h header file for the append operation. (0.5 points)

                   EXT     APPEND
                   ; Given R3 - points to a string s
                   ;       R4 - the character ch
                   ; May use R3-R7, conforms to standard calling conventions
                   ; If s.length < s.capacity and if ch != null
                   ;    then append ch to s, so that length grows by 1
   

   d) Suppose STR, a local variable, holds a string object. Write assembly code to append the letter c to the string. (0.5 points)

                   LEA     R3,R2,STR
                   LIS     R4,"c"
                   ADDSI   R2,R2,ARSIZE
                   LIL     R1,APPEND
                   JSRS    R1,R1
                   ADDSI   R2,R2,-ARSIZE
   

2. Background: There are some things missing from the descriptions of the string package above. Consider the problem of creating a string object called STR in the activation record of subroutine. This involves two separate pieces of assembly language code:
   • Defining STR as the offset of the object in the activation record, and setting aside space for it, and
   • Initializing the local variable.

   a) (0.5 points) Suppose I wanted to allocate STR as a local string variable with a capacity of 15 characters. What problem does this pose?

   The s.clear() operation sets the length to zero, but it provides no way to set the size or capacity of the string.

   b) (0.5 points) Suppose you have allocated STR as a local string variable large enough to store a 15 character string. How would you initialize it, given the description of the string class above, or if that description is missing something, describe the missing parts needed to solve this problem.

   As noted in part a), there is no operation in the string class to do this, we need a new operation. I suggest:
       s.init(capacity)
   This would set s.size to capacity+8 and s.length to zero.

   Note that problem 2a) is not a problem if STR is a global string variable. In that case, you can allocate and initialize the string as follows -- but note that this sets the capacity of the string variable equal to the length of its initial value:

   	COMMON	STR,STRSIZE
   OLDLC	=	.
   .	=	STR
   	STRINGCONST "initial value of string"
   STRSIZE =	. - STR
   .	=	OLDLC