CMSC216 Lab05: Bit Masking and Assembly Introduction

                           _________________

                            LAB05 QUESTIONS
                           _________________


Exercise Instructions
=====================

  Follow the instructions below to experiment with topics related to
  this exercise.
  - For sections marked QUIZ, fill in an (X) for the appropriate
    response in this file. Use the command `make test-quiz' to see if
    all of your answers are correct.
  - For sections marked CODE, complete the code indicated. Use the
    command `make test-code' to check if your code is complete.
  - DO NOT CHANGE any parts of this file except the QUIZ sections as it
    may interfere with the tests otherwise.
  - If your `QUESTIONS.txt' file seems corrupted, restore it by copying
    over the `QUESTIONS.txt.bk' backup file.
  - When you complete the exercises, check your answers with `make test'
    and if all is well, create a zip file with `make zip' and upload it
    to Gradescope. Ensure that the Autograder there reflects your local
    results.
  - IF YOU WORK IN A GROUP only one member needs to submit and then add
    the names of their group.


PROBLEM 1 Background on masking.c
=================================

  Study the code in `masking.c' which uses a number of bit-wise
  operations that have recently been discussed in lecture. These
  include:
  ,----
  | | Operation | Description          |
  | |-----------+----------------------|
  | | x & y     | Bit-wise And         |
  | | x | y     | Bit-wise Or          |
  | | x ^ y     | Bit-wise Xor         |
  | | ~x        | Bit-wise inversion   |
  | | x << y    | Bit-wise Left-shift  |
  | | x >> y    | Bit-wise Right-shift |
  `----
  Study the examples provided in `masking.c' and ensure you understand
  their meaning according to the context provided. Then answer the
  following questions.


Terminology
~~~~~~~~~~~

  - "Low order bits" or simply "the low bits" are written on the right
    side of binary numbers while "high order bits" appear on the
    left. The low/high distinction relates to the power of two
    associated with bits in that position.
  - "Bit indexes" start with 0 for the low order bit (right-most) and
    number up when moving to the left.  For example the number
    `0b10110001' has bits at the following indices:
    ,----
    | Value: 1011 0001
    | Index: 7654 3210  
    `----

    Bit index 0 is a "1" (the lowest order bit) and bit index 7 is also
    a 1 (the highest order bit).
  - "Setting" a given bit means to place a 1 in that position; "Set bit
    7" means to ensure that the 7th bit from the right is a 1
  - "Clearing" a give bit means to place a 0 at that position; "Clear
    bit 7" means to ensure that the 7th bit from the left is a 0


PROBLEM 1 QUIZ on masking.c
===========================

Shift with Or
~~~~~~~~~~~~~

  What is the effect of the following line of code:
  ,----
  | x = x | (1 << 19);
  `----

  - ( ) Changes `x' so that only its 19th bit is a 1, all other bits are
    0.
  - ( ) Changes `x' so that only its 19th bit is a 0, all other bits are
    unchanged.
  - ( ) Changes `x' so that its 19th bit is set to 1, all other bits
    unchanged.
  - ( ) Changes `x' so that its bits are shifted left by 19 places.


Shift with Or with Pattern
~~~~~~~~~~~~~~~~~~~~~~~~~~

  If `x' is cleared (value all 0's), what is the effect of the following
  line of code:
  ,----
  | x = x | (0b110101 << 8);
  `----

  - ( ) Sets the bits of `x' to the given pattern `0b110101' starting
    with the 8th position.
  - ( ) Checks that `x' has the given pattern `0b110101' starting with
    the 8th position.
  - ( ) Copies the given pattern `0b110101' 8 times throughout `x'
  - ( ) Adds 53 on the value of `x' faster than normal addition.


Shift with Invert with And
~~~~~~~~~~~~~~~~~~~~~~~~~~

  What is the effect of the following line of code:
  ,----
  | x = x & ~(1 << 8);
  `----

  - ( ) Changes `x' so that only its 8th bit is a 1, all other bits are
    0.
  - ( ) Changes `x' so that only its 8th bit is a 0, all other bits are
    unchanged.
  - ( ) Changes `x' so that its 8th bit is set to 1, all other bits
    unchanged.
  - ( ) Changes `x' so that its bits are shifted left by 8 places.


Shift with And
~~~~~~~~~~~~~~

  What is the effect of the following line of code:
  ,----
  | if( x & (1 << 13) ){ ... }
  `----

  - ( ) Conditionally execute only if the 13th bit of `x' is 0 and set
    that bit subsequently.
  - ( ) Conditionally execute only if the 13th bit of `x' is 0 but leave
    `x' unchanged.
  - ( ) Conditionally execute only if the 13th bit of `x' is 1 and set
    that bit subsequently.
  - ( ) Conditionally execute only if the 13th bit of `x' is 1 but leave
    `x' unchanged.


PROBLEM 1 CODE Complete masking.c
=================================

  Complete the TODO items in the `masking.c' file so that the missing
  blocks produce the effect mentioned in the `printf()' statements.

  The `masking.c' program ends with an interesting arrangement of bits
  that must be matched by writing some numbers in an `input.txt' file.
  Use GDB to help determine what numbers are appropriate and how they
  should be placed so that the "shot" is formed correctly to match the
  "target" leading to a program exit code of 0.

  Test that the code behaves correctly via the command
  ,----
  | make test-code testnum=1
  `----


PROBLEM 2 Background on asmbasics
=================================

  The `asmbasics_*' files allow for the construction of two executables
  which can be built via `make'.

  ,----
  | >> make
  | ...
  | >> ./asmbasics_c_only             # C only version, asmbasics_main.c and asmbasics_funcs.c
  | Let's explore Euclid's formula!
  | ...
  | 
  | >> ./asmbasics_mixed              # Mixed C/Assmebly version: asmbasics_main.c and asmbasics_funcs_asm.s
  | Let's explore Euclid's formula!
  | ...
  `----

  Both executables will do the same thing.
  - Accept to integer on the command line
  - Demonstrate a simple numerical relationship that Euclid worked out
    in the BC era.

  The intent of studying them is to get acquainted with how x86-64
  assembly instructions work by observing C code and equivalent assembly
  code then writing some assembly code that is equivalent to existing C
  code.

  Demoers will tour the slightly odd looking C code in
  `asmbasics_funcs.c' which are very short, arithmetically oriented
  functions. The code is written in an unusual style but one which
  matches the basic arithmetic operations that x86-64 Assembly
  instructions carry out making it easier to see the connection between
  C code and the provided assembly code. These appear in
  `asmbasics_funcs_asm.s' which is an x86-64 assembly source file.

  To pass automated tests, coders will need get a basic understanding of
  how assembly looks and works and then complete the TODO function in
  `asmbasics_funcs_asm.s'.


PROBLEM 2 QUIZ on asmbasics
===========================

  The function code in `asmbasics_funcs.c' looks a little odd because
  - ( ) It uses only operators like +=, *=, -= and so forth
  - ( ) It sets up an `ans' variable in each function to return a value
    rather than just returning something like a+b
  - ( ) Only two variables are used in any arithmetic expression;
    statements like `a = b+c;' do not appear
  - ( ) Actually all of these things are done and while readable, it
    seems inelegant

  On inspecting three provided assembly functions `difference, squared,
  squared_sum' in `asmbasics_funcs_asm.s', these show how many arguments
  and give them names by
  - ( ) Similar to C, they have a prototype like `difference(edi,esi)'
    which shows the registers storing the arguments but not their types
  - ( ) The parameter names are listed below the functions which looks a
    bit strange
  - ( ) They don't list how many and where parameters come in; it's the
    same for all functions and listed in documentation at the top of the
    file without anything in the function code giving clues about it
  - ( ) Trick question: it's actually not possible to pass parameters
    directly in assembly functions

  The equivalent of the `ans' variable used as the return variable in
  the C functions is this thing in x86-64 assembly:
  - ( ) The %eax register
  - ( ) The ret instruction
  - ( ) The %edi register
  - ( ) The addl instruction

  Which of the following is a valid sequence of instructions that will
  complete the `squared_diff' assembly function?
  ,----
  | squared_diff:
  |         movl  %eax, %edi              # (A)
  |         imull %edi, %edi
  |         imull %esi, %esi
  |         subl  %esi, %edi
  |         ret   %edi
  | 
  | squared_diff:
  |         movl  %edi, %eax              # (B)
  |         imull %eax, %eax
  |         imull %esi, %esi
  |         subl  %esi, %eax
  |         ret
  | 
  | squared_diff:
  |         movl  %eax, %edi              # (C)
  |         imull %eax, %eax 
  |         imull %esi, %esi 
  |         subl  %eax, %esi 
  |         ret
  | 
  | squared_diff:
  |         movl  %edi, %eax              # (B)
  |         imull %eax, %eax
  |         imull %esi, %esi
  |         subl  %esi, %eax
  |         ret   %eax
  `----
  - ( ) A
  - ( ) B
  - ( ) C
  - ( ) D


PROBLEM 2 CODE Complete asmbasics_funcs_asm.s
=============================================

  Complete the TODO portions of the code in `asmbasics_funcs_asm.s' and
  run the provided tests. The output should be identical to the behavior
  given when the C versions are run. Experiment with these two
  executables and compare their behavior if in doubt:
  - `asmbasics_c_only' : compiled with C code for main and functions
  - `asmbasics_mixed' : compiled with C code for main and assembly code
    for functions

  Test that the code behaves correctly via the command
  ,----
  | make test-code testnum=2
  `----