This lab should be done with an assigned partner. Here is the lab3 partner list.

First run update31, which will create the directory structure for your lab 3 assignment and copies over some starting point files:

$ update31
$ cd cs31/labs/03
$ pwd
/home/your_user_name/cs31/labs/03

Use the Makefile included in the starting point code!

---

Lab 3 Goals:

• writing functions in C, command line arguments, and C-style pass by reference.
• using the C bitwise operators to manipulate binary data
• disassembling code in gdb and describing its contents
• writing assembly code, and compiling it into an executable, running and testing it.

There are 4 parts to lab 3:

Your first task is to use bitwise operations to dissect two integers into their component bits to compare the count of "on" bits between the two values. In the file named bits.c implement a function named bitCompare that given two ints a and b, returns:

• a negative result if the bitwise representation of a has fewer 1s than the bitwise representation of b.
• a positive result if the bitwise representation of a has more 1s than the bitwise representation of b.
• or zero if both have the same number of 1s.

It should return a correct result for any possible pair of signed integer inputs.

Modify the main function in bits.c to make a call to your bitCompare function. Test out your function. Make sure it works for all combinations of positive, zero, and negative input values. You can use gdb to print out binary representations of integers to verify that your function is doing the right thing (remember gdb does not print out leading zeros):

(gdb) p/t (int)(1234)
(gdb) p/t (int)(-1234)

to compare, and print out the result of the bit-compare of the two values. Here are a few runs of a working program (yours does not need to print out the exact same positive and negative values as mine, but should print out a positive or negative when mine does):

./bits
usage: ./bits a b
./bits 7 8
bit compare result of 7(0x7) and 8(0x8) is 2
./bits -7 12
bit compare result of -7(0xfffffff9) and 12(0xc) is 28
./bits 4 6
bit compare result of 4(0x4) and 6(0x6) is -1
./bits 10 6
bit compare result of 10(0xa) and 6(0x6) is 0

Hints and Requirments

• You must use C bit-wise operations to determine if an individual bit is a 1 or a 0 in each of the int values passed to your bitCompare function.
• Remember that main has to have two parameters to access command line arguments:
  int main(int argc, char *argv[]) { ...
• You should be comparing the two values entered as command line arguments as their corresponding 4-byte int values (you are not comparing the number of bits in the string "1234" to the string "-56", but comparing the number of bits in the int value 1234 to those in the int value -56).
• atoi, can be used to convert a string of numbers to its equivalent int value:
  int x = atoi("1234"); // x gets int value 1234
• Your program should check that it is called with the correct number of command line arguments, and print out an error message and exit if not.
• use the Makefile
• See the week 4 weekly lab programs for some example programs that use command line arguments.
• See my C code style guide for information on good C programming style including comments and tips for how to not wrap lines.

(based on an assignment written by Julie Zelenski)

Bit vectors are often used to represent a set of (on/off or true/false) values in a space-efficient way. In a bit vector each individual bit represents the presence or absence of a particular value in the set. In this assignment you are going to encode and decode bit vectors that are used to maintain permission information associated with each Unix file.

Associated with every Unix file is a set of users (u:owner, g:group, o:other). With each user is a set of file access permissions (r: read, w: write, x:execute). In addition, a Unix file can be either a regular file or a directory. You can see file permissions in Unix by running ls -l. For example:

$ ls -l
-rw------- 1 newhall users    0 Sep 12 11:18 blah.c
-rw-r--r-- 1 newhall users   20 Sep 12 11:17 foo.c
drwxr-x--- 3 newhall users 4096 Sep 10 13:19 inclass/
drwx------ 4 newhall users 4096 Sep 10 13:19 labs/

This shows that blah.c and foo.c are regular files, and inclass and labs are directories (the d bit is set). It also shows the permissions for the three different groups in the following order (a dash means that the corresponding permission for a particular user is not granted):

directory  owner  group   other  linkcount  owner  group bytes date  filename
---------  -----  -----   -----  ---------  -----  ----- ----- ----  -------- 
   d        rwx    rwx     rwx
   -        rw-    r--     r--       1     newhall users  200   ...    foo.c  

The ls -l output above shows that the owner of the files (newhall), has read and write access to every file and directory listed, and execute access to the two directories (execute access is required to cd into a directory). The group (users) has read access to foo.c and read and execute access to inclass. And, all other users have read access to file foo.c.

To encode these 10 permission values in a bit vector requires two bytes of space (an unsigned short). The low-order 10 bits of the short value are used to encode the 10 values, the high-order 6 bits are unused:

unsigned short bit-vector:
     --------------------------------------------
     |    high-order byte |   low-order byte    |
     --------------------------------------------
bit:   15 ...  10    9   8|7 6    5 4 3    2 1 0     
         unused      d   r|w x    r w x    r w x
                         owner    group    other

The chmod command can be used to change the permission on a file. For example:

 chmod 640 foo.c

gives the owner read and write permission on foo.c, group read permission, and other no permissions (6 is 110 in binary corrsponding to 1 for the owner's read permission bit, 1 for the owner's write permission bit, and 0 for the owner's execute permission bit).

In a file named, filepermissions.c, you will implement two functions that encode and decode file permission bit vectors:

1. encodeFilePerms: this function has 5 parameters and returns 0 on success or -1 if an error occurs. An error could be invalid values passed in for one or more of the parameters, for example.

   The first 4 parameters are 4 int values representing the permissions: the first for the directory bit (a 0 or 1 value); the second for the owner permissions (0-7 value); the third for the group permissions (0-7 value); and the fourth for other permissions (0-7 value). The fifth parameter is an unsigned short passed by reference that the function will fill with the bit-vector encoding of the file permissions.

2. decodeFilePerms: this function takes two parameters: the first is an unsigned short bit-vector encoding file permissions; and the second is a string that the function will fill with 'd', 'r', 'w', 'x', or '-' characters based on the passed bit vector permission encoding. The string parameter should be constructed as follows based on the bit vector (include the space characters between each set to make it easer to read):

   d rwx rwx rwx   
   

   For example, if the bit vector encodes that the owner has read and write permission and that group has read permission, you would set the string parameter's contents to be:

   - rw- r-- ---
   

Your main function should take 4 command line options, all int values:

1. directory flag: (0 if file, 1 if directory)
2. owner permissions: a value between 0 and 7 (encoded like chmod values)
3. group permissions: a value between 0 and 7
4. other permissions: value between 0 and 7

Requirements and hints:

1. Your program when run should take 4 command line arguments, one for each permission and directory bit, for example:
   ./fileperms 0 6 4 4
2. main should have some error checking to ensure that the correct number of command line arguments have been passed to it. If not, it should print out an error message and exit.
3. main should make a call to your encodeFilePerms function, and if it was successful, print out the value of the short that encodes the file permissions (print in decimal and in hexadecimal). If not sucessful, main should print an error message and exit.
4. If encoding was successful, main should then call your decodeFilePerms function, passing in the bit vector encoding the file permissions, and a string to fill. main should print out the resulting string after the call.
5. Use the provided Makefile.

Here is output from a few runs of a working program:

./fileperms 
 ERROR: usage: ./fileperms dir_bit owner_perm group_perm other_perm
./fileperms 2 9 3 1
 ERROR: invalid permission inputs dir:2 owner:9 group:3 other:1
  dir must be (0:1), rest must be (0:7)....try again
./fileperms 1 7 5 5
encoding 1 7 5 5 is: 1005 (0x3ed)
the permission encoding of 0x3ed is: d rwx r-x r-x
./fileperms 0 6 4 0
encoding 0 6 4 0 is: 416 (0x1a0)
the permission encoding of 0x1a0 is: - rw- r-- ---

In the files you copied over when you ran update31, is a file named disassemble_code. It contains a set of 27 IA32 instructions that when executed in order, perform some operations on two local variables, x and y. Assume that x is located on the stack at address %ebp-4 and y at %ebp-8. Annotate the contents of this file in the following way:

For this part, you will starting with this file and editing it in vim to add content, incuding comments, stack contents, and a likely C-code translation of the IA32 instructions. In particular, do the following:

1. After each instruction (00 to 27) add a comment saying what the instruction is doing, and if it is doing something with x or y include that in your comment. For example, after instruction 00, I'd add something like:

     00:   movl   $0x3,-0x4(%ebp)   # store value 3 at mem location %ebp-4
                                    # (x <-- 3)   
     01:    shll   $0x2,-0x4(%ebp)
     ...
   

   (notice how I added another comment line between the two instructions to avoid line wrapping that is caused by lines longer than 80 characters)
2. As you trace through each instruction, indicate how the values of x and y on the stack are changed by indicating both the value, and which instruction changes it in parens. For example, since instruction 00 writes the value 3 to the stack address of x, I'd show that as follows:

   Stack
   =====
   esp-->
       y: 
       x:  3(00)  
   ebp-->
   

   If x's value is changed later, let's say at instruction 34 x is set to 7, I'd add the following:

       x:  3(00), 7(34)  
   

   After tracing through the code, the y: and x: lines should show a history of how those stack locations are changed by executing the IA32 instructions (showing the value(instruction_number) pair of each change).
3. Finally, at the bottom is a section for "C code equivalent". In this section, list the C-code equivalent to this assembly code (i.e. what C code could have been assembled to produce this IA32 code?). Be sure to use the variable names x and y in your C-code version. There certainly can be many correct answers to this part, and you are not required to be able to compile your C-code fragment to exactly the above code. The point is to give an example of how this IA32 code could map to C-code.

Refer to the IA32 cheat sheet, which has a summary of instructions, operand specifier modes, and registers. IA32 cheat sheet is also linked to in the Resources section of the CS31 webpage.

Your final task is to write an assembly code version of a function to swap two int values:

void swap(int *x, int *y);

For this part you will start with one of the file's you copied over, swap.s. This file already contains some code IA32 instructions that set up up and tear down the stack frame associated with the swap function. You will add IA32 instructions to the body of this IA32 function that perform the swapping operation.

main.c contains code to test our your swap function.

The Makefile has a rule to build an executable named swap from main.c and swap.s.

Hints and Requirements

• The basic stack set-up and return code is provided for you. However, if you need space for local variables on the stack frame, you need to explicitly add code to allocate the stack space you need by changing the value of %esp.
• The parameter values of x and y are on the stack in the caller's stack frame. They can be accessed relative to the %ebp pointer:

  esp ---->    # swap's stack frame:
  
  ebp ----> 
               # main's stack frame:
    ebp+0x8:   first parameter value 
    ebp+0xc:   second parameter value 
  

• Try implementing and testing incrementally. For example, first see if you can set the value pointed to by x to the value pointed to by y. Once that works, then see if you can add complete the function.
• You can use gdb (or ddd) to debug your solution. Set a breakpoint in swap, and use disass, ni, and print $reg to see values as you go. If you want to see the value referred to by an address, you need to tell gdb what type the address points to. For example, if you want to see an int value at address 0x1234, do:

  # re-cast address as an int pointer (int *), then dereference the pointer *
  (gdb) *(int *)(0x1234)  
  

Once you are satisfied with your solutions, hand them in by typing handin31 at the unix prompt.

Only one of you or your partner should run handin31 to submit your joint solutions If you accidentally both run it, send me email right away letting me know which of the two solutions I should keep and which I should discard (you don't want the grader to just guess which joint solution to grade).

You may run handin31 as many times as you like, and only the most recent submission will be recorded. This is useful if you realize, after handing in some programs, that you'd like to make a few more changes to them.