Assignment 3, due Feb 15

Solutions

Part of the homework for 22C:112, Spring 2008
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

  1. Background: Position independent machine code is code that can be moved from one range of memory addresses to another range of memory addresses without alteration. If all branches, jumps and calls within a block of code use program-counter relative addressing, and if references to constants embedded in the code use program-counter relative addressing, the control structure of the code is position independent. If, on the other hand, absolute memory addresses are used, these addresses will need modification if the code is relocated.

    a) If you know that the block of W words of code is currently loaded starting in address S (source) and it is to be moved to address D (destination), and you know that addresses S+X, S+Y and S+Z in the original code contain absolute memory addresses, what changes to the data must you make after copying the block of code from S to D. For simplicity, assume word addressing. (0.5 points)

    You must add the value D-S to the contents of memory addresses D+X, D+Y and D+Z.

    b) Suppose A and B are variables in C. Normally, to make A point to B, you would use A = &B. Having done this, we would use *A to reference B. This assumes that the type of A is *BT, where BT is the type of B. Give C code to assign a relative pointer to B to A and to follow that pointer. Get the computation right first, then worry about casting the expression. Note, the pointer in question is relative, but it is not PC relative. Rather, it should be relative to the address of A. (0.5 points)

    /* create the pointer, substitutes for A = &B */
    A = (BT *) ((long int) &B - (long int) &A);
    
    /* follow the pointer, substitutes for *A */
    *((BT *) ((long int) A + (long int) &A))
    

    The above is easier to understand if all the casting is removed so that all that remains is the raw arithmetic -- for which you must assume a typeless languge where pointers are just integers.

    c) Suppose you wanted the linker to generate PC relative addresses of external symbols when it linked two object files. Suggest a modification to Figure 7.17 that would allow this. For the sake of simplicity, assume 8 and 16-bit values. No need for 32-bit addresses here. (0.5 points)

    We need to add some new object record types. For example, consider

      1011 - load byte PC relative address of name, corrected by v bytes.
      1100 - load word PC relative address of name, corrected by v bytes.
    

    Given that V is the value from the object record, A is the absolute address of the named external symbol and P is the current address, (A-P)+V would be a reasonable PC relative load value. The offset V is needed because PC relative addresses frequently are offsets relative to an address just before or after the address where the displacement is loaded.

  2. Background: The Unix file system supports the notion of a polymorphic file type. There are files and directories, both of which are conceptually disk files. There are also sequential input files such as the keyboard, and sequential output files such as the (classical output-only) parallel ports. In addition, there are input-output devices such as the serial ports. Ignore other file types for the purpose of this assignment.

    The basic operations on a Unix file are lseek(), read(), and write(). See the man pages for these in section 2 of the programmer's reference manual (available online with the the man 2 lseek command, for example).

    A Question: Informally describe these using the concept of a class hierarchy, identifying all of the subclasses and noting which operations are applicable to each class in this hierarchy. Also note any problems posed by this hierarchy for the notion of class hierarchy as it is present in whatever object oriented programming languages you happen to be familiar with. (0.5 points)

    All of these operations are available for disk files. Sequential files such as the keyboard and printer cannot perform lseek. This suggests that the base class might have just read() and write(), while disk files have are instnces of a subclass that has the additional operation lseek().

    The problem is that the keyboard has only read() without write(), suggesting that bidirectional devices such as communications lines should be subclasses, while printers are output only, suggesting that the base class should support only the write() method.

    One way around this would be to use multiple inheritance, with two base classes, one read-only, one write-only, with a subclass representig read-write devices, and a subclass of that representing random-access read-write devices.

  3. Background: One popular Unix variant contains the following text in <stdio.h>:
    #define getc(p) (--(p)->_r < 0 ? _srget(p) : (int)(*(p)->_p++))
    #define getchar() getc(stdin)
    

    a) This is extraordinarily ugly C code! Using the terminology from the notes for lecture 10, explain what it is doing -- in one or two brief English sentences, and then explain why. Do not explain how it is doing it, that is a matter for part b. (0.5 points)

    Getchar() and getc() are macros. They get the next character from the stream buffer, unless the buffer has been exhausted, in which case, they call _srget() to both refill the buffer and get the first character from the buffer.

    b) Parse the definition of getc(), breaking it down by sub-expressions and briefly explaining each of them. (0.5 points)

    #define getc(p) (_cond(p) ? _then(p) : _else(p)) /* conditional expression */
    
    #define _cond(p) (_count(p) < 0)     /* compare count with zero */
    #define _count(p) (--_counter(p))    /* pre-decrement counter */
    #define _counter(p) ((p)->_r)        /* the _r field of the stream p */
    
    #define _then(p) (_srget(p))         /* call _srget on the stream */
    
    #define _else(p) ((int)(*_point(p))) /* return the character pointed to */
    #define _point(p) (_pointer(p)++)    /* post-increment the pointer */
    #define _pointer(p) ((p)->_p)        /* the _p field of the stream p */