Lab 1b: Data Representation in C

Assigned
Thursday, April 6, 2023
Due
Monday, April 17, 2023
Overview

Learning Objectives

Comfortably represent data in binary and hex.
Identify and recognize what a bit mask and operator does.
Extract useful information from bits using bit manipulation.
Recognize differences in C data types and use C casting.
Comfortably use pointers and arrays in C.
Understand and explain relation between pointers and arrays in C.

You will interact with a custom data representation for keeping track of things in a store, implementing functions using bitwise operators, pointers, and arrays.

Code for this lab
or in terminal:
wget https://courses.cs.washington.edu/courses/cse351/23sp/files/labs/lab1b.tar.gz

Unzip

Running tar xvf lab1b.tar.gz will extract the lab files to a directory called lab1b.

Instructions

Lab Format

This lab uses a custom data representation of aisles in a store.aisle_manager.c and store_client.c have skeleton functions for you to implement, each with a comment describing its desired behavior.

You will start by implementing functions that use bitwise operators, bitmasks, and C control structures to manage an individual aisle. After implementing these functions, you will move onto functions that use pointers, arrays, and your aisle functions to manage multiple aisles in a store. We have provided two test programs to help you check the correctness of your work (see Checking Your Work for more details).

As you work through the lab, you are encouraged to test each function one by one as you go (see Checking Your Work for instructions on how to just test one function).We also encourage you to use previously implemented functions and previously defined macros to help you solve future functions! Please post on the message board if you are unsure whether or not it is ok to use something.

Style

We will be checking your style - make sure you avoid the following common sources of bugs. This will be worth just 1 point and is intended to be relatively stress-free.

  • Magic numbers: You should not hard-code constants in your code when you can define and (re)use macros to give them meaningful names and consistent values.
  • Function usage: You should use defined functions when appropriate, especially the get_* and set_* functions.

Aisle Manager

Start by reading the description of an aisle's data representation at the top of aisle_manager.c. Make sure you fully understand the layout of the representation before continuing. If you have any questions, please post on the message board or come to office hours.

Once you understand the data representation, you can begin to implement the skeleton functions in aisle_manager.c. Do not be discouraged by the number of functions! They build gradually in level of difficulty, and many of them are similar to each other. Here's one recommended way of working through the file:

Start by filling in the macros at the top of the file with various bitmasks to be used later.
Continue by implementing the get_* and set_* functions.
Finish by implementing the rest of the functions related to manipulating the items in an aisle.

Here is a list of functions that need to be implemented:

get_section
get_spaces
get_id
set_section
set_spaces
set_id
toggle_space
num_items
add_items
remove_items
rotate_items_left
rotate_items_right

At this point you should be able to pass all tests in the aisle_test executable! Now you can move onto store_client.c

Store Client

store_client.c has some functions for interacting with a group of aisles and a stockroom in the store. It uses a global array with elements of type unsigned long to represent multiple aisles. It uses a global array with elements of type int to represent a stockroom for the store (items stowed away that are not in the aisles). We have not talked about C global variables in depth, but for the purpose of this assignment, you can treat them as you would global variables in Java. That is, you can use the global variables in any of the functions as though they were local variables, without declaring them as local variables. There are slight differences between global variables in C and Java, but they are not relevant for this assignment.

Here is a list of functions that need to be implemented:

refill_from_stockroom
fulfill_order
empty_section_with_id
section_with_most_items

At this point you should be able to pass all tests in the store_test executable! This means you are done with the programming part of the assignment (don't forget about the synthesis questions!).

Checking Your Work

We have included the following tools to help you check the correctness of your work:

We have included the functions print_binary_long and print_binary_short, which take an unsigned long and unsigned short, respectively, and output its binary representation. These can be useful in debugging your code, but their use is optional and all calls to the functions should be commented out in your final submission.Here is a usage example for print_binary_long (print_binary_short works similarly except it takes an unsigned short as its argument):

You can also use printf to debug your functions, but you'll have to include a line with #include <stdio.h> at the top of your file. Its use is optional, and all calls to the function should be commented out in your final submission.

aisle_test and store_test are programs that check the functional correctness of the code in aisle_manager.c and store_client.c, respectively. To build and use them, type the following two commands:

$ make
$ ./aisle_test
$ ./store_test

Notice that you must rebuild aisle_test and store_test each time you modify your code. (You can rebuild them by typing make.) You may find it helpful to work through the functions one at a time, testing each one as you go. You can use the -f flag to instruct aisle_test and store_test to test only a single function:

$ ./aisle_test -f set_id
$ ./store_test -f section_with_most_items

aisle_test and store_test first test your solution on specific cases, and then on a wide range of inputs. As a manner of limiting the test output, for the range of inputs the testing program will only print out the first input that your solutions are incorrect for (or no input if you pass all cases).

There is some partial credit awarded if your function passes the specific cases but not the range of cases, and each function is tested separately to allow for the opportunity for partial credit should you only complete some of the functions.

Lab 1b Synthesis Questions

Make sure your answers to these questions are included in the file lab1Bsynthesis.txt!

Data representation: Your friend suggests an alternative data representation for sections in an aisle. In this representation, the lowest 8 bits would be used to store an integer representing the number of items in a section, and the upper 8 bits would be used to store a unique item id. Compared to our current representation, give at least three benefits and at least one drawback of this new representation.  [4 pt]

Number representation: Consider the following two statements:

y = -1;

y = 0xFFFFFFFF;

Note that the type of y is purposefully omitted. Is there a difference between using these two statements in your code? Explain. If there is a difference, make sure to provide an example.  [2 pt]

Floating point: Explain why comparing two floating point numbers with == or != is problematic. The suggested equality alternative from lecture involved comparing the difference against a threshold value: what considerations would go into this choice?  [3 pt]

Submission

Be sure to run make clean then make on your code before submitting! Submissions that don't compile will automatically receive a score of ZERO.

Submit your completed aisle_manager.c, store_client.c, and lab1Bsynthesis.txt files to the "Lab 1b" assignment on Gradescope.

After submitting, please wait until the autograder is done running and double-check that you passed the "File Check" and "Compilation and Execution Issues" tests. If either test returns a score of -1, be sure to read the output and fix any problems before resubmitting. Failure to do so will result in a programming score of 0 for the lab.

It is fine to submit multiple times up until the deadline, we will only grade your last submission. NOTE that if you do re-submit, you MUST RE-submit all THREE files again (aisle_manager.c, store_client.c, and lab1Bsynthesis.txt).