Problem Set 3, Boolean Logic & Basic MIPS Instructions

Due Sunday, January 30 @ 11:59PM

Submit your answers to blackboard. Be sure to show your work (if necessary).

  1. One logic function that is used for binary addition is exclusive OR. The output of a two-input exclusive OR function is true only if exactly one of the inputs is true. Show the truth table for a two-input exclusive OR function and implement (draw) this function using AND gates, OR gates, and inverters (aka NOT gates).
  2. Consider the following MIPS-like instructions.
    add f, g, h
    add f, f, 1
    add f, g, h
    For the MIPS-like instructions above, what is a corresponding C statement?
  3. Below is a short listing of C statements. Assume that the variables f, g, h, i and j below are assigned to registers $s0, $s1, $s2, $s3, and $s4, respectively. Assume that the base addresses of arrays skis and snowboards are stored in registers $s6 and $s7, respectively.
    f = g + h + snowboards[4];
    f = g - skis[snowboards[4]];
    For the C statements above, what is the corresponding MIPS assembly code?
  4. Below is a short listing of MIPS assembly instructions. Assume that the variables in a C program f, g, h, i and j are assigned to registers $s0, $s1, $s2, $s3, and $s4, respectively. Assume that the base addresses of arrays called breakups and makeups are stored in registers $s6 and $s7, respectively.
    add $s0, $s0, $s1
    add $s0, $s0, $s2
    add $s0, $s0, $s3
    add $s0, $s0, $s4
    lw $s0, 4($s6)
    For the MIPS assembly instructions above, what is the corresponding C statement?
  5. How many registers were needed to carry out the MIPS assembly above in question #4?

    6. Rubric (50 points)

    1. XOR, your new BFF:
      XOR 0 1
      0 0 1
      1 1 0
    2. As many of you noticed, the first and last instructions "overwrite" the value of f, so to speak. So this simply becomes: f = g + h;
    3. The first one is easy, but remember that MIPS is 32-bit byte-addressed, so the offset must be multiplied by 4:
      add $s0, $s1, $s2
      lw $t0, 16($s7)
      add $s0, $s0, $t0
      The second one is a little tricky, since we're using a value in one array as the offset for another array. There are different solutions to this, but given only the use of add instructions:
      lw $t0, 16($s7)
      add $t0, $t0, $t0 # $t0 is now twice its original value
      add $t0, $t0, $t0 # $t0 is now four times its original value
      add $t1, $s6, $t0 # take the base address of skis, add the calculated offset $t0
      lw $t2, 0($t1) # no offset, since $t1 is the base address of skis plus the offset we calculated and stored in $t0
      add $s0, $s1, $t2
    4. To keep things straight in my head, I would rewrite the MIPS instructions to "MIPS-like" instructions substituting the variable names provided (eg, add $s0, $s0, $s1 becomes add f, f, g). In the end, you simply get:
      f = f + g + h + i + j;
      f = breakups[1];
    5. Simply count the registers used: 5 for the adds, and one more for the lw.