CS5600 Lab1: Setup and C review

Lab1 comprises two parts:

• Part 1: Setup and tools
• Part 2: C review

The first part serves as a warming-up phase for you to familiarize yourself with the environment and tools you will use this semester. The second part helps you practice coding in the C programming language. If you know C, this part will help you remember; if you don’t know C, this is an excellent opportunity to learn C, an elegant language.

There is a lot to read but not too many lines of code to write. Quote from the Labs page, “if a lab is at first confusing even in its instructions, please don’t be discouraged; understanding the instructions is part of the work of the labs!”

Part 1: Setup and tools

We are going to use git and Linux virtual machine for distributing and collecting assignments.

Section 0: GitHub

If you don’t have a GitHub account, sign up for one here. You only need a Free plan for the labs.

Section 1: Setup a Linux VM

In this course, all of our programming assignments will be assessed on a Linux virtual machine (VM). You can think of a virtual machine as a way to run a particular operating system (in our case, an instance of Ubuntu) on top of another operating system (the one that controls your laptop or desktop).

We recommend

• VirtualBox, which runs on Windows, Linux, and MacOS (with x86 CPUs) and has been successfully used in this class for many years;
• VMwmare Fusion Player, if you use Apple machines with M1/2 chips. (How do I know if I’m using M1/2 chips? Check here.)

You have two options to start your Lab1:

Option 1: use VirutalBox CS5600 VM image (X86 CPUs).

CS5600 staffs have prepared a ready-to-use VM image for you. To choose this option:

1. download and install VirtualBox: be sure to download the package that is appropriate for your system. Once it has downloaded, install it by double clicking on the installer and following the prompts. The default settings for installation are generally the right ones.
2. download the pre-built VM image from OneDrive. The link and instructions are on Canvas homepage. This is a zipped file. You need to unzip before use.
3. run the VM by double clicking the image file or importing the image in the VirtualBox.
4. Note: you can find VM’s sudo password on Canvas homepage.
5. (optional) Watch this video from 13:15, you will see how to run a terminal and update packages (you don’t have to update the packages). The video also explains some basics of Linux and C.

Notes:

• If you are using Apple M1/2 chips, you need to choose option 2 (see below).
• For Mac users, you may face a permission problem when installing VirtualBox. See the solution here. Or, if you see “The Installation Failed”, see here.

Option 2: use VMware Fusion CS5600 VM image (ARM CPUs).

This option is for students who use Apple M1/2 chips.

1. register a free Personal User License of VMware Fusion Player 13. Go to VMware Fusion Player; select “License & Dowload” tab; click “create an account” (if you don’t have one); follow the instructions to create a VMware account; login your account; go to VMware Fusion Player again to get your Personal User License.
2. on the same page, download and install VMware Fusion Player 13 by clicking “Manually Download” under tab “License & Download”.
3. download the pre-built VMware VM image from OneDrive. The link and instructions are on Canvas homepage. This is a zipped file. You need to unzip before use.
4. run the VM by double clicking the image file or importing the image to the VMware Fusion Player.
5. Note: you can find VM’s sudo password on Canvas homepage.
6. (optional) Watch this video from 13:15, you will see how to run a terminal and update packages (you don’t have to update the packages). The video also explains some basics of Linux and C.

Of course, besides VirtualBox and VMware Fusion Player, if you have an Ubuntu/Debian installed, you can use it as well. But, notice that we may need you to install packages and update environments in later labs. We strongly recommend you to use a VM, so that you don’t have to mess up your working environment.

See some useful links/references about Linux command line and C in the end of this page¹.

Section 2: Git and GitHub

What is git?

Git was developed by Linus Torvalds for development of the Linux kernel. It’s is a distributed version control system, which means it supports many local repositories which each track changes and can synchronize with each other in a peer-to-peer fashion. It’s the best widely-available version control system, and certainly the most widely used. For information on how to use git, see:

• Eddie Kohler’s excellent notes on git
• GitHub Guides: Git Handbook

For the workflow in GitHub:

• GitHub Guides: Hello World

Cloning the lab1 repository

Please click the GitHub Lab1 link on Canvas homepage to create your own private clone of the lab1 repository; this clone lives on (is hosted by) GitHub. Once that clone exists, you will perform a further clone to get that private repository onto your devbox (your VM). You’ll do your work on your devbox, and then push your work to the GitHub-hosted private repository for us to grade.

Here’s how it should work.

1. Click the GitHub Lab1 link on Canvas homepage to create your Lab1 clone on GitHub.
2. Log in to your GitHub.
3. Provide a name.
4. The link should automatically clone the repository. For instance, if your username name was foobar, you should now have a repository on your GitHub called NEU-CS5600-labs/lab1-foobar.

Teaching GitHub about your identity

The easiest way to access GitHub repositories is using an SSH key, a secret key stored on your CS5600 VM that defines your identity. Follow the steps below to create a key for your virtual machine.

1. Enter your VM: double click the image or start the VM in VirtualBox/VMware Fusion Player.

2. Open Terminal.

3. Run $ ssh-keygen -t rsa -b 2048 (don’t copy the $ sign) and follow the instructions.

   • Press enter to use the default file path and key name (should be ~/.ssh/id_rsa).
   • Choose a password or leave it empty.

   This creates your ssh keys, which live in the directory ~/.ssh. Your public key is in the file ~/.ssh/id_rsa.pub.

4. Run cat .ssh/id_rsa.pub to display your public key.

5. Copy your public key (that is, select the text on the screen, and copy it to the clipboard).

6. In GitHub, go to your profile settings page (accessible via the upper-rightmost link–this looks like a bunch of pixels for new accounts). Select “SSH and GPG keys” and hit the “New SSH key” button. Then copy and paste the contents of your ~/.ssh/id_rsa.pub (from the VM) into the “Key” section. Give the key a sensible title, hit the “Add SSH key” button, and you’re good to go.

Creating a local clone

Once GitHub knows your SSH identity, you’re ready to clone your lab repository and start doing work! Here’s how to get a local clone of your private repo on your machine:

1. Enter your VM and open a terminal

2. Configure your git “identity” as it shows up in commits:

    $ git config --global user.name "FIRST_NAME LAST_NAME"
    $ git config --global user.email "YOUR_@COLLEGE_EMAIL"
   

3. Clone your lab1 repo:

    $ cd ~
    $ git clone git@github.com:NEU-CS5600-labs/lab1-<Your-GitHub-Username>.git lab1
   

   Note that the git@github.com:... can be obtained on GitHub by clicking the “Clone or download” button. You want to clone using SSH, not HTTPS, so you might need to click “Use SSH”.

4. Look at the files in the repo:

    $ cd ~/lab1/
    $ ls
   

   You should see:

    part1           part2           slack.txt
   

Exercise 1 compile and run hello world.

• compile and run the helloworld

$ cd ~/lab1/part1/
$ gcc -o hello hello.c
$ ./hello

• Now you should see

hello world

GCC (gcc in the above example) is a widely used compiler. In the above command, -o specifies the output file (namely, hello) and hello.c is the source file to be compiled. See a quick introduction of gcc here. In this course, you don’t have to be an expert of gcc. We will provide compiling supports for labs. (Nevertheless, having some understanding of how gcc works is helpful.)

Section 3: Debugging

This part of the lab will give you practice on debugging.

Navigating to syntax errors

Try to compile a program debug:

$ cd ~/lab1/part1/
$ make

make is a system to organize compilation. When you run make, the compilation system will look for a file named Makefile and executes the rules within. Take a look at our simple Makefile which compiles the program debug (you can open it using your favorite text editor). We put comments to explain things. Again, you don’t have to be an expert of make, and here is a quick introduction.

After running make, you will see some errors. This is because the code has a syntax error; thus, it cannot be compiled.

Exercise 2 Fix two errors.

1. Use the compiler’s error message to determine what’s wrong (a syntax error). After you fix the syntax error, the code will compile. Try make again:

   $ make
   

   Now, you should be able to compile but with a warning message debug.c:10:12: warning ....

2. Run debug. You will see:

   $ ./debug
   double a number (10) is (0)
   debug: debug.c:50: main: Assertion 'num + num == doub_num' failed.
   Aborted (core dumped)
   

   Though our code compiled, but it was not correct. It failed on an assertion (num + num == doub_num). Read debug.c to fix this problem and let the program pass the assertion.
   Hints:

   • Warning information is useful.
   • This error is a typo. You should be able to fix the problem by changing only one line of code.

After fixing the two errors, you should be able to see:

double a number (10) is (20)
Segmentation fault (core dumped)

Aha! Our code passes the assertion, but it is still not correct (core dumps are bad). Specifically, the segmentation fault means that our program issued an illegal memory reference, and the operating system ended our process. Making matters worse, we have no idea what the problem in the code is. In the following section, you will learn how to use gdb to debug this kind of problem.

Debugging with gdb

Run gdb: Use the GNU debugger, or gdb to run the program:

$ gdb debug
(gdb)

Set breakpoints: One thing that you might want to do is to set a breakpoint before the program begins executing. Breakpoints are a way of telling gdb that you want it to execute your program and then stop, or break, at a place that you define. Use the following command to set a breakpoint at the main function:

(gdb) b main
Breakpoint 1 at 0x155f: file debug.c, line 46.

Run the program: Then use gdb’s command run to actually start the program (this is the general pattern in gdb: one invokes the debugger, perhaps sets a breakpoint, and then starts the program with run):

(gdb) run

Backtrace: The program will be stopped when it reaches the breakpoint. At this point, you will be presented with gdb’s command prompt again. To see the “call stack” (or stack trace), which is the list of functions that have called this one—literally, the stack frames on top of the current one—you issue backtrace or bt for short:

(gdb) bt

Experienced developers will often ask for a stack trace as step 0 or 1 of understanding a code problem. Get in the habit of asking gdb to give you a backtrace.

Continue running: To make the program continue running after a breakpoint, use continue, or c for short:

(gdb) c

Step through the code: Of course, if you just c every time you hit a breakpoint, then you will lose control of the program. You often want the command next, or n:

(gdb) n

This “executes” the next line of code, for example executing an entire function. (The command step executes a single line of C code. There is little difference between step and next unless you are about to enter a function. step steps into the function; next “steps over” the function.)

Inspect the values of variables: In gdb’s command prompt, the program is stalled. You can query the program’s current global and local variables with the print command, or p for short.

Run gdb on debug. Set a breakpoint at the function process_msg. At this breakpoint, determine the value of the argument mem:

(gdb) print mem
$1 = 0xc0000000c <error: Cannot access memory at address 0xc0000000c>

This means that variable mem holds a value 0xc0000000c (note that you may see a different value here. Why? Take a look at the type of mem.).

Aside: you can check local variables’ names using:

(gdb) info local

Core dump: If a program terminated abnormally (for example, debug), the state of the program will be recorded by the OS and (if core dumps are enabled) saved in a so-called core dump. gdb can use a core dump to inspect a crash situation.

To debug using core dumps, you must first enable core dumps, and then point gdb at the relevant file. We’ll do this in several steps:

// specify the core dump file
$ sudo sysctl -w kernel.core_pattern=core
// enable core dumps
$ ulimit -c unlimited 

$ ./debug
$ ls -l core
$ gdb ./debug core

The idea here is that the core file gives gdb enough information to recover the memory and CPU state of the program at the moment of the crash. This will allow you to determine which instructions experienced the error.

Exercise 3 Fix segfault.

• Use gdb and core dump file to study the segfault and fix the bug.
• Again, the bug is a typo. You should be able to fix the bug with one line of code change.

After fixing the typo, you should be able to see:

$ ./debug
double a number (10) is (20)
processed msg: HELLO WORLD!

Section 4: C string and memory overflow

Though it seems that debug works fine, there is a deeper bug that is related to manipulating strings and memory. Run the AddressSanitizer version of debug:

$ make
$ ./debug-mem-check
double a number (10) is (20)
=================================================================
==4236==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60200000001c at pc 0x7f616e8a8a6d bp 0x7ffed4d8ad90 sp 0x7ffed4d8a538
... // more error messages

Memory checker—AddressSanitizer

AddressSanitizer is a tool to detect buffer overflow and memory corruption bugs. debug-mem-check is compiled from debug.c and AddressSanitizer (read Makefile to see how we compile debug-mem-check).

C string

In C, a string (e.g., "hello!") is a sequence of chars with a trailing zero (\0). A C string is also called a Null-terminated string. The ending \0 is used for recognizing the end of a string.

For example, a string “hello!” in memory would look like:

------------------------------
| h | e | l | l | o | ! | \0 |
------------------------------

Given a string (char * str = "hello!"), we can tell the length of the string by strlen. In particular, strlen is a library function returns the number of characters that precede the terminating NULL character (see function details by $ man strlen). Namely, strlen(str) returns 6.

The deeper bug

The bug detected by AddressSanitizer is a combination of incorrect manipulating strings and memory. Here are some hints: think of invoking strlen on a string without trailing \0. What will happen? strlen will look for the ending \0 and go way beyond the end the string until it finds a ‘\0’ (which belongs to other data) or reaching some illegal memory.

Exercise 4 pass debug-mem-check

Fix the deeper bug and pass debug-mem-check. After fixing the bug, you should see:

$ make
./debug-mem-check
double a number (10) is (20)
processed msg: HELLO WORLD!

Section 5: Saving changes by committing

As you modify the skeleton files to complete the labs, you should frequently save your work to protect against laptop failures and other unforeseen troubles, and to create “known good” states. You save the changes by first “committing” them to your local lab repo and then “pushing” those changes to the repo stored on github.com.

$ git commit -am "saving my changes"
$ git push origin

Note that whenever you add a new file, you need to manually tell git to “track it”. Otherwise, the file will not be committed by git commit. Make git track a new file by typing:

$ git add <your-new-file>

After you’ve pushed your changes by typing git push origin, they are safely stored on github.com. Even if your laptop catches on fire in the future, those pushed changes can still be retrieved. However, you must remember that doing git commit by itself does not save your changes on github.com (it only saves your changes locally). So, don’t forget to type git push origin.

To see if your local repo is up-to-date with your origin repo on github.com and vice versa, type git status.

Exercise 5 commit and push.

1. go to the lab1 folder cd ~/lab1/
2. commit your modifications git commit -am"my CS5600 first commit"
3. push to github.com, git push origin

4. You should see something like:

    Counting objects: ...
    ....
    To ssh://github.com/NEU-CS5600-labs/lab1-<username>.git
     7337116..ceed758  main -> main
   

This completes the part 1.

Part 2: C review

This lab will give you practice in the C programming language. For those who know C, this will reinforce your prior experience; for others, this is a good opportunity for you to learn C. The overall comfort you’ll gain (or reinforce) with C language and the Linux computing environment will be helpful for future labs.

Part2 has three main sections:

1. Implementing a simple cipher.
2. Implementing a linked queue.
3. Implementing a ciphered queue using the cipher and the queue.

Challenge: there are two challenges in Lab1. They are optional. If you successfully finish them, you will get extra credits.

Section 0: C, text editor, and cloning Lab1

C programming language

All of the CS5600 projects will be done in C, for two main reasons. First, some of the things that we want to implement require direct manipulation of hardware state and memory, which are operations that are naturally expressed in C. Second, C are widely used languages (still!), so learning them is a useful thing to do in its own right.

If you are interested in why C looks like it does, we encourage you to look at Ritchie’s history. Here, perhaps, is the key quotation: “Despite some aspects mysterious to the beginner and occasionally even to the adept, C remains a simple and small language, translatable with simple and small compilers. Its types and operations are well-grounded in those provided by real machines, and for people used to how computers work, learning the idioms for generating time- and space-efficient programs is not difficult. At the same time the language is sufficiently abstracted from machine details that program portability can be achieved.”

If you want to master C, one book is (probably) enough:

• The C programming language (second edition), Brian W. Kernighan and Dennis M. Ritchie. Prentice Hall, Inc., 1988. ISBN: 0-13-110362-8.

Here is another useful link:

• C Tutorial: https://www.cprogramming.com/tutorial/c-tutorial.html

A good text editor is essential

If you’re using a good editor on your desktop (such as Sublime Text or Atom), then you can continue using them. If you are not doing so already, begin using a powerful text editor. We recommend vim (or emacs). vim is already installed on the pre-built VM. If you want to install emacs, do: sudo apt-get install -y emacs.

Then, to edit:

$ vim myfile.txt
// or
$ emacs myfile.txt

Most of our instructions below will be with reference to vim, so you may wish to use that one.

To get started, work through either this vim tutorial or the emacs tutorial that is built into emacs. (From within emacs, you can pull up the tutorial by typing C-h t. This is read as “press ctrl-h, then let go, then press t”).

Then spend some time just navigating and editing sample text (perhaps doing this lab, perhaps writing notes to your friends that you later copy into email). You may feel at first that these editors are slowing you down (“how do I exit vim???”; you’re not alone, see a hilarious blog post here), but comfort and fluency with them will pay off in the long term. It’s worth slowing down and “learning proper technique.” You’ll find that within a day or so, you’ll have the required keystrokes internalized, and within a few days, you’ll probably be faster at common editing tasks.

Checking Part2 contents

1. Start your VM and open the VM’s terminal.
2. Check contents:

   $ cd ~/lab1/part2/
   $ ls -F
   
   // you should see:
   Makefile                ciphered_queue_main.c   queue.h
   caesar.c                examples/               queue_main.c
   caesar.h                lab1-shell-APIs.txt     tests/
   caesar_main.c           queue.c
   

3. We provide test cases for Part2. The unit tests are written in Python (python3). If you don’t have python3 installed, run $ sudo apt install python3.

Note: all the shell commands below happen within the folder ~/lab1/part2.

Section 1: Ciphers

Encryption is a method that encodes a normal message (called plaintext) into a secret code (called ciphertext) that hides the original message’s true meaning. To encode a message, a cipher includes a variable, called key, that makes a cipher’s output unique.

The Caesar Cipher (try it online here) is the earliest and simplest cipher. It takes any integer value as a key and replaces each letter of the plaintext with a different letter of the alphabet which is key positions further away in the alphabet. For example, if key = 3, then A is encoded by D, B is encoded by E, … X is encoded by A, Y is encoded by B, and Z is encoded by C.

Read and understand file caesar.h and caesar.c, then compile the code by:

$ make
gcc -o caesar -Wall -pedantic -fstack-protector-all -fsanitize=address caesar.c caesar_main.c -I.
gcc -o queue -Wall -pedantic -fstack-protector-all -fsanitize=address queue.c queue_main.c -I.
gcc -o ciphered_queue -Wall -pedantic -fstack-protector-all -fsanitize=address caesar.c queue.c ciphered_queue_main.c -I.

Run the compiled program to see the results:

$ ./caesar

// You should see the outputs:
Usage: ./caesar [encode|decode] <number> <string>

Exercise 1 finish encode(...).

• Fill in function encode(...) that encodes the string plaintext using the Caesar cipher. It shifts characters by the given number of positions.

• You can assume that the input text only includes uppercased letters, lowercased letters, and numbers. These three categories (uppercased letters, lowercased letters, and digits) form three “Caesar Cipher loops”: with a shift of one position, 'Z' => 'A', 'z' => 'a', and '9' => '0'.

• Test your code (compile and run):

  $ make
  $ ./caesar encode 1 ABC
    
  // the correct output should be
  BCD
  

Exercise 2 finish decode(...).

• Fill in the function decode(...) that decodes the ciphertext string using the Caesar cipher by shifting the characters back by key positions.

• Test your code.
  NOTE: whenever you modify the code, you need to compile the code (i.e., make) for the update to take effect.

  $ make
  $ ./caesar decode 1 BCD
    
  // the correct output should be
  ABC
  

Exercise 3 capture illegal characters.

• You might have noticed that we made an assumption about the inputs (they are either letters or numbers), but what if the inputs are not what we want?

• Update your encode(...) function to produce an error message when encountering illegal characters:
  • if the input string contains any character that is not [A-Z | a-z | 0-9], then function encode(...) returns “ILLCHAR” (a string) as the output.
  • does your code properly handle the case that the input string is shorter than “ILLCHAR”? (for example, “+” as input)
• Test your code.

  $ make
  $ ./caesar decode 1 +
    
  // the correct output should be
  ILLCHAR
  

Now, with all functions implemented, you should test your caesar with more test cases (that we provide) and figure out if your code has bugs.

$ make test1

// If you pass all test cases, you should see:
[RUN] Project0Runner.decode_alphabet_lower_upper
[OK] Project0Runner.decode_alphabet_lower_upper
[RUN] Project0Runner.decode_alphanumeric
[OK] Project0Runner.decode_alphanumeric
[RUN] Project0Runner.decode_numbers
[OK] Project0Runner.decode_numbers
[RUN] Project0Runner.encode_alphabet_lower_upper
[OK] Project0Runner.encode_alphabet_lower_upper
[RUN] Project0Runner.encode_alphanumeric
[OK] Project0Runner.encode_alphanumeric
[RUN] Project0Runner.encode_numbers
[OK] Project0Runner.encode_numbers
All test cases passed!!!

If you fail some test cases, our script will provide the failed input, the expected output, and your output (which should be different from the expected output). You can use the information for debugging.

Section 2: Linked Queue

In operating systems, queues are used widely. For example, processes are represented using a specific data structure that contains all the information related to the process (identifier, etc). The scheduler keeps track of processes to schedule using a linked queue.

Read and understand file queue.h and queue.c. The type node_t represents a node in a queue that has both a pointer (node_t *) to the next node and a piece of data (char[]). The type queue_t represents a queue with a head and a tail pointing to the first and the last node in the queue.

Compile the code and run:

$ make
$ ./queue

// you should see
Usage: ./queue <file>

Read queue_main.c and understand how the program works. The program queue needs a file as input. Let’s feed the program with an example file called ./examples/q_case.txt:

$ ./queue ./examples/q_case.txt

// you should see:
cmd: enqueue ABC
cmd: dequeue
cmd: enqueue BDE
cmd: dequeue
cmd: dequeue
cmd: enqueue CS
cmd: enqueue 5600
finally: 

A couple of things to keep in mind:

• You will have to allocate memory for new nodes (by using malloc).
• Don’t forget to free the memory that you allocate!
• Use $ man <function-name> to check useful C functions. (See usage of man by $ man man!)
• You are free to add other structures or functions in your implementation.
• C does not have classes, it is a procedural language, but it does have struct (see queue.h) for grouping together several data items into a new type. Types can be given new names using typedef. By convention, they are usually named ending with a _t.

Exercise 4 implement queue.c

1. Fill in the function enqueue(...) that adds elements to the end of the queue.

2. Fill in the function void * dequeue(...) that removes and returns the element at the front of the queue. Notice that the return value is a general pointer (void *) and you are free to return whatever you want. For example, possible options include returning the node, returning the data in the node, etc.

3. Implement free_queue(...).

4. Implement print_queue(...).

5. Hint: char *data is supposed to point to a NULL-terminated string.

Exercise 5 fill in queue_main.c

1. Read the “section 3” of lab1-shell-APIs.txt carefully. This document explains the expected input-output format of Lab1. It is crucial to follow the APIs because TA’s grading code interacts with your code via these APIs. If you code does not follow them, the grading tools will think your code is incorrect (hence losing points).

2. Fill in the function process_line(...) in queue_main.c.

Test your queue implementation by running make test2. If you pass all test cases, you should see:

$ make test2

[RUN] Project2Runner.empty_enqueue_test
[OK] Project2Runner.empty_enqueue_test
[RUN] Project2Runner.large_enqueue_op_test
[OK] Project2Runner.large_enqueue_op_test
[RUN] Project2Runner.regular_pass_test
[OK] Project2Runner.regular_pass_test
[RUN] Project2Runner.regular_print_test
[OK] Project2Runner.regular_print_test
All test cases passed!!!

Section 3: Ciphered Queue

In this section, you will combine the Caesar cipher and the queue to build a ciphered queue, in which nodes’ data may be encrypted. For the ciphered queue, you will reuse your previous Caesar cipher and queue implementations.

Read file ciphered_queue_main.c, compile, and run.

$ make
$ ./ciphered_queue

// you should see:
Usage: ./ciphered-queue <file>

// run with an example file
$ ./ciphered_queue ./examples/cq_case.txt

// you should see:
cmd: encode_enqueue 1 ABC
cmd: dequeue
cmd: encode_enqueue 1 ABC
cmd: dequeue_decode 1
cmd: encode_enqueue 1 A+C
cmd: dequeue_decode 1
cmd: enqueue CS
cmd: enqueue 5600
cmd: encode_enqueue 1 CS
cmd: encode_enqueue 1 5600
finally: 

Exercise 6 complete ciphered_queue_main.c.

1. Read the “section 4” of lab1-shell-APIs.txt carefully. Again, it is important to strictly follow the input-output specifications.

2. Implement function encode_enqueue(...) and dequeue_decode(...).

3. Fill in function process_line2(...).

A clarification of two erroneous cases. There are two “erroneous” cases (illegal characters and invalid commands). Your program ciphered_queue should behave differently:

1. when meeting an invalid command (e.g., “enqueue” with no arguments), your program should ERROR-and-stop: (1) print “ERROR\n” on screen and (2) quit gracefully (remember to free memory!)

2. when the plaintext for encode_enqueue is invalid (e.g., encode_enqueue 1 A+C; notice “+” is an illegal character), you should store something special in the node. What we (the grading script) expect is to see an “ILLCHAR” as an output when the program dequeue or dequeue_decode the node. (your program should not stop in this scenario.)

Test your code ciphered_queue by running make test3. If you pass all test cases, you should see:

$ make test3

[RUN] Project3Runner.empty_enqueue_test
[OK] Project3Runner.empty_enqueue_test
[RUN] Project3Runner.large_enqueue_op_test
[OK] Project3Runner.large_enqueue_op_test
[RUN] Project3Runner.regular_pass_test
[OK] Project3Runner.regular_pass_test
All test cases passed!!!

Make sure you pass all the test cases before submitting Lab1 (otherwise, you will lose points). Our grading scripts will have more test cases.

Lab1 Challenges

There are two challenges for Lab1. Challenge 1 and 2 are 5 and 15 points, respectively (out of 100 of Lab1).

Challenge I support larger data string.

(Optional) In our current implementation, the data string size in a node is limited to 127 bytes (why not 128? see here). Can you support strings with no length limits? That is however long a data string is, you queue can save it, as far as hardware allows.

Note: increasing 128 to 256, or any other large numbers, doesn’t work. (which is also a waste of memory!)

Challenge II add undo to the ciphered queue.

(Optional) Add a new commands undo to your implementation of ciphered queue.

• undo applies to the status of the queue. It cancels the effectiveness of the last command (encode_enqueue, dequeue_decode, enqueue, or dequeue).
• multiple, say n, undo will cancel the most recent n commands.
• If there is no command to undo, undo will do nothing.
• Here is an example. Given an input file:

  encode_enqueue 1 ABC
  encode_enqueue 1 DEF
  dequeue_decode 1
  undo
  dequeue_decode 1
  undo
  undo
  

  the output (on screen) should be:

  ABC    // output of the first dequeue_decode
  ABC    // output of the second dequeue_decode
  finally: [BCD]   // "encode_enqueue 1 DEF" is undoed
  

Finally, submit your work

Submitting consists of three steps:

1. Executing this checklist:
   • Fill in ~/lab1/slack.txt with (1) your name, (2) your NUID, (3) slack hours you used, and (4) if you have taken challenges.
     Note: you have to specify that you finished the challenges. Otherwise, we will assume you didn’t.
   • Make sure that your code build with no warnings.
   • Make sure you have added (git add) all files that you created.

2. Push your code to GitHub:

    $ cd ~/lab1
    $ git commit -am 'submit lab1'
    $ git push origin 
   
    Counting objects: ...
     ....
     To ssh://github.com/NEU-CS5600-labs/lab1-<username>.git
      7337116..ceed758  main -> main
   

3. Actually commit your lab (with timestamp and git commit id):

   1. Get the git commit id of your work. A commit id is a 40-character hexadecimal string. You can obtain the commit id for the last commit by running the command git log -1 --format=oneline.

   2. Paste both your git repo address and the commit id (the hexadecimal string) to Canvas. In Canvas, there will be an assignment for this lab. You should paste the git repo address and the commit id in two lines:

       git@github.com:NEU-CS5600-labs/lab1-<username>.git
       29dfda9c788fade33421f242b5dd1ff5295fd3c9
      

      Notice: the repo address must start with git@github.com:... (not https://...). You can get your repo address on GitHub repo page by clicking the green “Code” button, then choose “SSH”.

   3. Note: You can submit as many times as you want; we will grade the last commit id submitted to Canvas. Also, you can submit any commit id in your pushed git history; again, we will grade the commit id submitted to Canvas.

NOTE: Ground truth is what and when you submitted to Canvas.

• A non-existent repo address or a non-existent commit id in Canvas means that you have not submitted the lab, regardless of what you have pushed to GitHub—we will not grade it. So, please double check your submitted repo and commit id!

• The time of your submission for the purposes of tracking lateness is the timestamp on Canvas, not the timestamp on GitHub.

This completes the lab.

Acknowledgments

Some links in Part1 were borrowed from prior CS5600s (2020fall and 2021spring). A large portion of this writeup was borrowed from Mike Walfish’s CS202, which further borrowed materials from Harvard’s CS61, Jinyang Li’s CS201, and Aurojit Panda’s 3033. Skeleton code in part 2 is created by Peter Desnoyers, with modifications by the CS5600 staff.