Don’t Freak Out About These Midterm Review Questions

2. Expressions

QUESTION 2A. Here are eight expressions. Group the expressions into four pairs so that the two expressions in each pair have the same value, and each pair has a different value from every other pair. There is one unique answer that meets these constraints. m has the same type and value everywhere it appears (there’s one unique value for m that meets the problem’s constraints). Assume an x86 machine.

1. sizeof(&m)
2. -1
3. m & -m
4. m + ~m + 1
5. 16 >> 2
6. m & ~m
7. m
8. 1

5. Hello program

Now that Shintaro has represented the image in memory as an array of uint16_t objects, he can manipulate the image using C. For example, here’s a function.

void swap(void) {
   for (int i = 0; i < 16; ++i)
      cute[i] = (cute[i] << 8) | (cute[i] >> 8);
}

Running swap produces the following image:

Shintaro has written several other functions. Here are some images (A is the original):

A		B		C		D		E
F		G		H		I		J

For each function, what image does that function create?

QUESTION 5A.

void f0() {
   for (int i = 0; i < 16; ++i)
      cute[i] = ~cute[i];
}

QUESTION 5B.

void f2() {
   for (int i = 0; i < 16; ++i) {
      cute[i] = ((cute[i] >> 1) & 0x5555) | ((cute[i] << 1) & 0xAAAA);
      cute[i] = ((cute[i] >> 2) & 0x3333) | ((cute[i] << 2) & 0xCCCC);
      cute[i] = ((cute[i] >> 4) & 0x0F0F) | ((cute[i] << 4) & 0xF0F0);
      cute[i] =  (cute[i] >> 8)           |  (cute[i] << 8);
   }
}

QUESTION 5C.

void f3() {
   char *x = (char *) cute;
   for (int i = 0; i < 16; ++i)
      x[2*i] = i;
}

For “fun”

The following programs generated the other images. Can you match them with their images?

void f3() {
   for (int i = 0; i < 16; ++i)
      cute[i] &= ~(7 << i);
}

void f4() {
   swap();
   for (int i = 0; i < 16; ++i)
      cute[i] <<= i/4;
   swap();
}

void f5() {
   for (int i = 0; i < 16; ++i)
      cute[i] = -1 * !!(cute[i] & 64);
}

void f6() {
   for (int i = 0; i < 16; ++i) {
      int tmp = cute[15-i];
      cute[15-i] = cute[i];
      cute[i] = tmp;
   }
}

void f7() {
   for (int i = 0; i < 16; ++i)
      cute[i] = cute[i] & -cute[i];
}

void f8() {
   for (int i = 0; i < 16; ++i)
      cute[i] ^= cute[i] ^ cute[i];
}

void f9() {
   for (int i = 0; i < 16; ++i)
      cute[i] = cute[i] ^ 4080;
}

8. Data structures

Here are four assembly functions, f1 through f4.

f1:
    movl    4(%esp), %eax
    movl    8(%esp), %ecx
    testl   %ecx, %ecx
    jle .L2
    xorl    %edx, %edx
.L3:
    movl    4(%eax), %eax
    incl    %edx
    cmpl    %ecx, %edx
    jne .L3
.L2:
    movl    (%edx), %eax
    ret

f2:
    movl    8(%esp), %edx
    leal    0(,%edx,4), %ecx
    movl    4(%esp), %eax
    movl    (%eax,%ecx), %eax
    addl    %ecx, %eax
    movl    (%eax), %eax
    ret

f3:
    pushl   %esi
    pushl   %ebx
    movl    12(%esp), %ecx
    movl    16(%esp), %esi
    movl    20(%esp), %eax
    testl   %esi, %esi
    jle .L9
    xorl    %edx, %edx
.L10:
    movl    %eax, %ebx
    andl    $1, %ebx
    movl    4(%ecx,%ebx,4), %ecx
    incl    %edx
    sarl    %eax
    cmpl    %esi, %edx
    jne .L10
.L9:
    movl    (%ecx), %eax
    popl    %ebx
    popl    %esi
    ret

f4:
    movl    8(%esp), %edx
    movl    4(%esp), %eax
    movl    (%eax,%edx,4), %eax
    ret

QUESTION 8A. Each function returns a value loaded from some data structure. Which function uses which data structure?

1. Array
2. Array of pointers to arrays
3. Linked list
4. Binary tree

QUESTION 8B. The array data structure is an array of type T. Considering the code for the function that manipulates the array, which of the following types are likely possibilities for T? Circle all that apply.

1. char
2. int
3. unsigned long
4. unsigned long long
5. char *
6. None of the above