CSC373 Final Examination - Spring 2011

Answer all problems.

---

1. In the following questions assume the variables x and y are 32 bit signed integers and that the machine uses two's complement representation.

   Match each of the descriptions on the left with a line of code on the right (write in the letter).

   a.	-x
   b.	~x
   c.	x & y
   d.	x * 7
   e.	!x
   f.	(x < 0) ? 1 : -1

   A. ~(~x & ~y)

   B. ~(~x | ~y)

   C. ((x >> 31) | ((~x + 1) >> 31)) + 1

   D. ~x + 1 + (x << 3)

   E. ~x + 1

   F. (x << 2) + (x << 1)

   G. x >> 31

   H. ((~x >> 31) & ~1) + 1

   I. x ^ ~0

   J. x ^ 0

    

2. The sizeof(T) function returns the size in bytes of a value of type T. For example, sizeof(char) is 1, sizeof(short) is 2, sizeof(int) is 4, sizeof(double) is 8. Since the size of any type is never negative, the return type of sizeof is unsigned int.

   int main()
   {
     int x = 0xFFFFFFFF;
   
     if ( x < sizeof(int) ) {
       printf("yes");	      
     } else {
       printf("no");
     }
     return 0;
   }
   

   1. What is the output of the program?

   2. Briefly explain your answer:

      Since the type of sizeof(int) is unsigned, the x value 0xFFFFFFFF is converted to unsigned and the comparison is between unsigned values. 0xFFFFFFFF is the largest possible unsigned value so the comparison is false and "no" is printed.

3. Truncation, Sign Extension

   For some initial values of x at line 1, the value of x after line 3 is not the same as the initial value depending on truncation and sign extension.

       1   int x = 0x00A1B2C4;
       2   short s = x;   
       3   x = s;         
   	

   What are the final values of s and x in hex?

   s =

   x =

4. A 32 bit IEEE floating point number x has the format

   s	e	f
   1	8	23

   Fill in the missing entries in the table below that gives the conditions on fields e and f for each floating point number type.

   type	e value	f value
   denormalized		any value
   normalized
   infinity	all 1's
   NaN

5. Here are two loops. For each loop indicate whether it is an infinite loop (i.e., will not terminate) or not.

   A.

    int x;
    float sum = 0;
    for(x = 100; x > 0; x = x + x) {
         sum = sum + x;
    }
   	    

   Is this an infinite loop?

   Briefly explain your answer:

   Eventually overflow occurs for x = x + x and x becomes negative, which terminates the loop.

   B.

    float x;
    float sum = 0;
    for(x = 100.0; x > 0.0; x = x + x) {
         sum = sum + x;
    }
   	    

   Is this an infinite loop?

   Briefly explain your answer:

   Eventually, the x value becomes inf and from that point on x = x + x will still result in x being inf. For x == inf, x > 0.0 so the loop never terminates.

6. A C function, f is compiled to the following IA32 assembly code.

   
   f:
   	pushl	%ebp
   	movl	%esp, %ebp
   	subl	$16, %esp
   	movl	$0, -8(%ebp)
   	movl	$1, -4(%ebp)
   	jmp	.L2
   .L3:
   	movl	-4(%ebp), %eax
   	addl	%eax, -8(%ebp)
   	addl	$1, -4(%ebp)
   .L2:
   	movl	-4(%ebp), %eax
   	cmpl	8(%ebp), %eax
   	jle	.L3
   	movl	-8(%ebp), %eax
   	leave
   	ret
   

   This function references the memory locations on the stack. The table below arbitrarily assigns some names to these locations.

   Stack Memory Location	Assigned Name for this Location
   8(%ebp)	n
   -4(%ebp)	x
   -8(%ebp)	y

   Write the C code for this function f using the variable names assigned above for the stack memory locations.

   Give the return type, the name of the function and its parameter and then write the body of the function.

   You may use C's goto label to translate assembly jump instructions. Or you may convert the jumps to C standard control statements (if , for loops, or while loops), as long as your code will execute with the same result as the original assembly code.

   // Goto Version y = 0; x = 1; goto L2 L3: y = y + x; x++; L2: if (x <= n) goto L3 return y; // Goto converted to standard C control stmts y = 0; x = 1; while(x <= n) { y = y + x; x++; } return y;

7. Consider the following datatype definition of a C struct on an IA32 (x86) machine.

   typedef struct {
     char  c;
     double *p;
     int i;
     double d;
     short s;
   } struct1;
   	

   1. Fill in the following table giving the size of each member, the offset in bytes from the beginning of the struct for each member, and the number of padding bytes (0 - 7) to maintain alignment requirements.

      Assume the alignment rules are as in Windows: data types of size X must be aligned on X-byte boundaries.

      Member	Offset	Member Size (bytes)	Padding (0 - 7 bytes)
      c
      p
      i
      d
      s

   2. Including the padding, how many bytes should be allocated for this struct?

   3. What is the alignment of this struct; that is, it should begin at an address that is a multiple of what value (1, 2, 4, or 8)?

      Ans:

8. The following problem concerns basic cache lookups.

   • The memory is byte addressable.
   • Memory accesses are to 1-byte words (not 4-byte words).
   • Physical addresses are 13 bits wide.
   • The cache is 2-way set associative, with a 4 byte line size and 16 total lines.

   In the following tables, all numbers are given in hexadecimal. The contents of the cache are as follows:

   Two-Way Set Associative Cache
   Index	Tag	Valid	0	1	2	3	Tag	Valid	0	1	2	3
   0	09	1	86	30	3F	10	00	0	99	04	03	48
   1	45	1	60	4F	E0	23	38	1	00	BC	0B	37
   2	EB	0	2F	81	FD	09	0B	0	8F	E2	05	BD
   3	06	0	3D	94	9B	F7	32	1	12	08	7B	AD
   4	C7	1	06	78	07	C5	05	1	40	67	C2	3B
   5	71	1	0B	DE	18	4B	6E	0	B0	39	D3	F7
   6	91	1	A0	B7	26	2D	F0	0	0C	71	40	10
   7	46	0	B1	0A	32	0F	DE	1	12	C0	88	37

   For the given physical address, indicate the cache entry accessed and the cache byte value returned in hex.

   Indicate whether a cache miss occurs.

   If there is a cache miss, enter "-" for "Cache Byte returned".

   Physical address: 0E34

   Block Byte Offset
   Cache Set
   Cache Tag
   Cache Hit? (Y/N)
   Cache Byte Returned

---