15-213 Fall '98, Final Exam Official solution 

---------------------------------------------------------------------------
PROBLEM 1.

many correct answers, e.g.,
mask = (2 << high) - (1 << low);

---------------------------------------------------------------------------
PROBLEM 2.

for (i=0; (i<len) && (a[i] != val); i=i+1)

---------------------------------------------------------------------------
PROBLEM 3.

a. no
b. no
c. 2^64 entries, possible return values = {0,1}
d. infinite loop, no explosion
e. 2 explodes, 11 defuses, 1381 explodes, 5071 defuses

---------------------------------------------------------------------------
PROBLEM 4.

/* Compute 2**x */
float fpwr2(int x) {
  union {
    unsigned u;
    float f;
  } result;
  unsigned exp;
  unsigned sig;
  if (x < -149) {
    /* Too small.  Return 0.0 */
    exp = 0;
    sig = 0;
  } else if (x < -126) {
    /* Denormalized result */
    exp = 0;
    sig = 1 << (x + 149);
  } else if (x < 128) {
    /* Normalized result. */
    exp = x + 127;
    sig = 0;
  } else {
    /* Too big.  Return +oo */
    exp = 255;
    sig = 0;
  }
  result.u = exp << 23 | sig;
  return result.f;
}

---------------------------------------------------------------------------
PROBLEM 5.

a) 0/24 | 24/1 | 26/2 | 32/8 | 40/16 | 56/32
b) 44/b.i[1] | -40/a[1][1],a[1][2] | 24/c[0][1]

---------------------------------------------------------------------------
PROBLEM 6.

a. vpn: 07, ok: n, exp: TLB hit/PT miss
b. vpn: 0d, ok: y, exp: TLB hit/PT hit, PPN=2d
c. vpn: 09, ok: y, exp: TLB miss/PT hit, PPN=17
d. vpn: 3f, ok: n, exp: aliased with VPN 02
e. vpn: 1e1, ok: n, exp: invalid VPN

---------------------------------------------------------------------------
PROBLEM 7.

a. 
dst		src
m m m m		m m h m
m m m m		m h m h
m m m m		m m h m
m m m m		m h m h

b.
dst		src
m h h h		m h h h
m h h h		m h h h
m h h h		m h h h
m h h h		m h h h

---------------------------------------------------------------------------
PROBLEM 8.

a. packet # (doubles as rot(n) encryption)
   port #
   length
   (padding)
   (payload)

b.
struct packet {
  unsigned int seqnum;
  unsigned int port;
  unsigned short len;
  unsigned short placeholder;
  unsigned char payload[1];
};

c.
00 01  00  00 | 00 00  00  19 | 01 2C | 00 00 | payload!