Homework 06: Pointers, Arrays, Strings

The goal of this homework assignment is to allow you to practice using pointers, arrays, and strings in C99. The first activity involves building a string utilities library, while the second activity requires you to use this library to build a str utility similar to tr.

For this assignment, record your source code and any responses to the following activities in the homework06 folder of your assignments GitLab repository and push your work by noon Saturday, March 24.

Activity 0: Preparation

Before starting this homework assignment, you should first perform a git pull to retrieve any changes in your remote GitLab repository:

$ cd path/to/repository                   # Go to assignments repository

$ git checkout master                     # Make sure we are in master branch

$ git pull --rebase                       # Get any remote changes not present locally

Next, create a new branch for this assignment:

$ git checkout -b homework06              # Create homework06 branch and check it out

You are now ready to work on the activities below.

Activity 1: String Utilities Library (10 Points)

In Python, we had the luxury of strings being first-class objects with all sorts of useful methods such as str.lower or str.strip. Unfortunately, strings in C are just arrays that utilize the sentinel pattern for denoting the end of the strings and the standard library is a bit bare when it comes to manipulating strings.

To rectify this situation, for the first activity you are to create a string utilities library, libstr, which contains functions such as str_lower and str_strip which implement some of the functionality present in Python but lacking in C99.

Starter Code

To help you get started, the instructor has provided you with the following starter code:

# Download starter code tarball
$ curl -LO https://www3.nd.edu/~pbui/teaching/cse.20289.sp18/static/tar/homework06.tar.gz

# Extract starter code tarball
$ tar xzvf homework06.tar.gz

Once downloaded and extracted, you should see the following files in your homework06 directory:

homework06
    \_ Makefile                   # This is the Makefile for building all the project artifacts
    \_ README.md                  # This is the README file for recording your responses
    \_ library.c                  # This is the C99 implementation file for the string utilities library
    \_ main.c                     # This is the C99 implementation file for the string utility
    \_ str.h                      # This is the C99 header file for the string utilities library
    \_ test_libstr.py             # This is the Python test script for the string utilities library
    \_ test_str.py                # This is the Shell test script for the string utility

The details on what you need to implement are described in the following sections.

Task 0: `str.h`

The str.h file is the header file for the string utilities library, which means it contains the function prototypes:

/* str.h: string utilities library */

#pragma once

#include <stdbool.h>
#include <stdlib.h>

/* Case */
char *  str_lower(char *s);
char *  str_upper(char *s);

/* Comparison */
bool    str_startswith(const char *s, const char *t);
bool    str_endswith(const char *s, const char *t);

/* Strip */
char *  str_chomp(char *s);
char *  str_strip(char *s);

/* Reverse */
char *  str_reverse(char *s);

/* Translation */
char *  str_translate(char *s, char *from, char *to);

/* Integer Conversion */
int     str_to_int(const char *s, int base);

/* vim: set sts=4 sw=4 ts=8 expandtab ft=c: */

Other programs will #include this file in order to use the functions we will be implementing in this library.

Note: For this task, you do not need to modify this file. Instead, you should review it and ensure you understand the provided code.

Task 1: `Makefile`

The Makefile contains all the rules or recipes for building the project artifacts (e.g. libstr.a, libstr.so, etc.):

CC=       gcc
CFLAGS=   -g -gdwarf-2 -Wall -std=gnu99
LD=       gcc
LDFLAGS=  -L.
AR=       ar
ARFLAGS=  rcs

TARGETS=  libstr.a \
          libstr.so

all:      $(TARGETS)

test:
        @$(MAKE) -sk test-all

test-all: test-libstr

test-libstr:  libstr.so test_libstr.py
        curl -sLO https://gitlab.com/nd-cse-20289-sp18/cse-20289-sp18-assignments/raw/master/homework06/test_libstr.py
        chmod +x test_libstr.py
        ./test_libstr.py -v

test-str: str-static str-dynamic test_str.sh
        curl -sLO https://gitlab.com/nd-cse-20289-sp18/cse-20289-sp18-assignments/raw/master/homework06/test_str.sh
        chmod +x test_str.sh
        ./test_str.sh

clean:
        rm -f $(TARGETS) *.o

# TODO: Add rules for libstr.a libstr.so

# TODO: Add rules for str-dynamic str-static

For this task, you will need to add rules for building the static library libstr.a and the shared library libstr.so. Besure to have a recipe for any intermediate object files that both libraries require.

Makefile Variables

You must use the CC, CFLAGS, LD, LDFLAGS, AR, and ARFLAGS variables when appropriate in your rules. You should also consider using automatic variables such as $@ and $< as well.

Once you have a working Makefile, you should be able to run the following commands:

# Build all TARGETS
$ make
gcc -g -gdwarf-2 -Wall -std=gnu99 -fPIC -c -o library.o library.c
ar rcs libstr.a library.o
gcc -L. -shared -o libstr.so library.o

# Run all tests
$ make test
test_00_str_lower (__main__.StrTestCase) ... FAIL
test_01_str_upper (__main__.StrTestCase) ... FAIL
test_02_str_startswith (__main__.StrTestCase) ... FAIL
test_03_str_endswith (__main__.StrTestCase) ... FAIL
test_04_str_chomp (__main__.StrTestCase) ... FAIL
test_05_str_strip (__main__.StrTestCase) ... FAIL
test_06_str_reverse (__main__.StrTestCase) ... FAIL
test_07_str_translate (__main__.StrTestCase) ... FAIL
test_08_str_to_int (__main__.StrTestCase) ... FAIL
   Score 1.96
...

# Remove generated artifacts
$ make clean
rm -f libstr.a libstr.so *.o

Note: The tests will fail if you haven't implemented the string utilities library.

Warnings

You must include the -Wall flag in your CFLAGS when you compile. This also means that your code must compile without any warnings, otherwise points will be deducted.

Task 2: `library.c`

The library.c file contains the C99 implementation for the string utilities library.

For this task, you will need to implement the following functions:

char * str_lower(char *s)

This function converts all the letters in s to lowercase (e.g. s.lower() in Python)

Hint: Use tolower to convert a char to lowercase.
char * str_upper(char *s)

This function converts all the letters in s to uppercase (e.g. s.upper() in Python).

Hint: Use toupper to convert a char to uppercase.
bool str_startswith(char *s, char *t)

This function determine whether or not s starts with t (e.g. s.startswith(t) in Python)

Hint: Consider how you know when you are done checking t.
bool str_endswith(char *s, char *t)

This function determine whether or not s ends with t (e.g. s.endswith(t) in Python).

Hint: Use strlen to get the length of the string.
char * str_chomp(char *s)

This function removes a trailing newline character from s if one is present (e.g. s[:-1] if s[-1] == '\n' else s in Python).

Hint: Use strlen to get the length of the string.
char * str_strip(char *s)

This function removes any whitespace from the front and back of s (e.g. s.strip() in Python).

Hint: Use two reader and writer pointers to modify the string.
char * str_reverse(char *s)

This function reverses the letters in s (e.g. s[::-1] in Python).

Hint: Considering how to swap two chars.
char * str_translate(char *s, char *from, char *to)

This function translates the letters in s using the mapping provided by from and to (e.g. s.translate(string.maketrans(from, to)) in Python).

Hint: Construct and then utilize a lookup table.
int str_to_int(char *s, int base)

This function converts s into an integer with the provided base (e.g. int(s, base) in Python).

Hint: Process each individual digit from right to left.

Requirements

The functions above must perform modifications in-place (if necessary). That is, you must not allocate any additional temporary strings as scratch space. Moreover, you should not need to use the heap or dynamic memory allocation.
The functions above must run in O(n) (ie. linear) time and use O(1) (ie. constant) space.

The functions above must only use pointers when accessing or iterating through a string. That is, you cannot index into a string:

/* Allowed: Iterate through string using pointers */
for (char *c = s; *c; c++)
    putc(*c, stdout);

/* Forbidden: Iterate through string using array index */
for (size_t i = 0; i < strlen(s); i++)
    putc(s[i], stdout);

Task 3: `test_libstr.py`

As you implement the functions in library.c, you should use the test_libstr.py script to test each function:

# Build artifacts
$ make

# Run test script manually
$ ./test_libstr.py -v
test_00_str_lower (__main__.StrTestCase) ... ok
test_01_str_upper (__main__.StrTestCase) ... ok
test_02_str_startswith (__main__.StrTestCase) ... ok
test_03_str_endswith (__main__.StrTestCase) ... ok
test_04_str_chomp (__main__.StrTestCase) ... ok
test_05_str_strip (__main__.StrTestCase) ... ok
test_06_str_reverse (__main__.StrTestCase) ... ok
test_07_str_translate (__main__.StrTestCase) ... ok
test_08_str_to_int (__main__.StrTestCase) ... ok
   Score 9.00

----------------------------------------------------------------------
Ran 9 tests in 0.001s

OK

Alternatively, you can both build the artifacts and run the test script by doing the following:

# Build and run test scripts
$ make test

To use Python to interactively test a function, you can do something like the following:

# Import ctypes package
>>> import ctypes

# Load string utilies shared library
>>> libstr = ctypes.CDLL('./libstr.so')

# Set return type for str_lowercase
>>> libstr.str_lower.restype = ctypes.c_char_p

# Call str_lowercase function
>>> libstr.str_lower(b'Hello, World!')
b'hello, world!'

Of course, you are free to create your own test programs to debug and test your string utilities library.

Iterative Development

You should practice iterative development. That is, rather than writing a bunch of code and then debugging it all at once, you should concentrate on one function at a time and then test that one thing at a time. The provided unit tests allow you to check on the correctness of the individual functions without implementing everything at once. Take advantage of this and build one thing at a time.

Task 4: `README.md`

In your README.md, respond to the following prompts:

What is the difference between a shared library such as libstr.so and a static library such as libstr.a?
Compare the sizes of libstr.so and libstr.a, which one is larger? Why?

Activity 2: Str Utility (5 Points)

Once you have a working string utilities library, you are to complete the str utility:

$ ./str-static -h                                             # Display usage
Usage: ./str-static SOURCE TARGET

Post Translation filters:

    -s          Strip whitespace
    -r          Reverse line
    -l          Convert to lowercase
    -u          Convert to uppercase
    -t FILTER   Only include lines that start with FILTER
    -d FILTER   Only include lines that end with FILTER

$ echo "   Hello World" | ./str-static                        # Just echo input
   Hello World

$ echo "   Hello World" | ./str-static -s                     # Strip whitespace
Hello World

$ echo "   Hello World" | ./str-static -r                     # Reverse letters
dlroW olleH

$ echo "   Hello World" | ./str-static -l                     # Lowercase
   hello world

$ echo "   Hello World" | ./str-static -u                     # Uppercase
   HELLO WORLD

$ echo "   Hello World" | ./str-static -s -t Hello            # Strip and starts with Hello
Hello World

$ echo "   Hello World" | ./str-static -d World               # Ends with World
   Hello World

$ echo "   Hello World" | ./str-static 'aeio' '4310'          # Translate
   H3ll0 W0rld

$ echo "   Hello World" | ./str-static -s -l 'aeio' '4310'    # Translate, strip, and lowercase
h3ll0 w0rld

The str utility must use the corresponding functions from the string utilities library you created above to translate and filter the input text.

Task 1: `Makefile`

The first task is to modify the Makefile to include additional rules for the following targets:

str-static: This is a static executable of main.c.
str-dynamic: This is a dynamic executable of main.c.

Once again, be sure to add any rules for any intermediate object files.

Additionally, be sure to add str-static and str-dynamic to the all recipe and to add test-str to the test-all recipe.

Once you have a working Makefile, you should be able to run the following commands:

# Build all TARGETS
$ make
gcc -g -gdwarf-2 -Wall -std=gnu99 -fPIC -c -o library.o library.c
ar rcs libstr.a library.o
gcc -L. -shared -o libstr.so library.o
gcc -g -gdwarf-2 -Wall -std=gnu99 -c -o main.o main.c
gcc -L. -o str-dynamic main.o -lstr
gcc -L. -static -o str-static main.o -lstr

# Run all tests
$ make test
test_00_str_lower (__main__.StrTestCase) ... ok
test_01_str_upper (__main__.StrTestCase) ... ok
test_02_str_startswith (__main__.StrTestCase) ... ok
test_03_str_endswith (__main__.StrTestCase) ... ok
test_04_str_chomp (__main__.StrTestCase) ... ok
test_05_str_strip (__main__.StrTestCase) ... ok
test_06_str_reverse (__main__.StrTestCase) ... ok
test_07_str_translate (__main__.StrTestCase) ... ok
test_08_str_to_int (__main__.StrTestCase) ... ok
   Score 9.00

----------------------------------------------------------------------
Ran 9 tests in 0.001s

OK
Testing str utility...
 str -h                                   ... Success
 str -h (valgrind)                        ... Success
 str                                      ... Success
 str (valgrind)                           ... Success
 str aeio 4310                            ... Success
 str aeio 4310 (valgrind)                 ... Success
 str -s aeio 4310                         ... Success
 str -s aeio 4310 (valgrind)              ... Success
 str -r aeio 4310                         ... Success
 str -r aeio 4310 (valgrind)              ... Success
 str -l aeio 4310                         ... Success
 str -l aeio 4310 (valgrind)              ... Success
 str -u aeio 4310                         ... Success
 str -u aeio 4310 (valgrind)              ... Success
 str -t H3ll0 aeio 4310                   ... Success
 str -t H3ll0 aeio 4310 (valgrind)        ... Success
 str -d SP4C3 aeio 4310                   ... Success
 str -d SP4C3 aeio 4310 (valgrind)        ... Success
 str -l -u aeio 4310                      ... Success
 str -l -u aeio 4310 (valgrind)           ... Success
 str -r -u -t 0r3h aeio 4310              ... Success
 str -r -u -t 0r3h aeio 4310 (valgrind)   ... Success
   Score 3.00

# Remove generated artifacts
$ make clean
rm -f libstr.a libstr.so str-dynamic str-static *.o

Task 2: `main.c`

The main.c file is contains the C99 implementation of the string utility described above:

/* main.c: string library utility */

#include "str.h"

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Globals */

char *PROGRAM_NAME = NULL;

/* Modes */

enum {
    /* TODO: Enumerate Modes */
};

/* Functions */

void usage(int status) {
    fprintf(stderr, "Usage: %s SOURCE TARGET\n\n", PROGRAM_NAME);
    fprintf(stderr, "Post Translation filters:\n\n");
    fprintf(stderr, "   -s          Strip whitespace\n");
    fprintf(stderr, "   -r          Reverse line\n");
    fprintf(stderr, "   -l          Convert to lowercase\n");
    fprintf(stderr, "   -u          Convert to uppercase\n");
    fprintf(stderr, "   -t FILTER   Only include lines that start with FILTER\n");
    fprintf(stderr, "   -d FILTER   Only include lines that end with FILTER\n");
    exit(status);
}

void translate_stream(FILE *stream, char *source, char *target, char *filter, int mode) {
    /* TODO: Process each line in stream by performing transformations */
}

/* Main Execution */

int main(int argc, char *argv[]) {
    /* TODO: Parse command line arguments */

    /* TODO: Translate Stream */

    return EXIT_SUCCESS;
}

/* vim: set sts=4 sw=4 ts=8 expandtab ft=c: */

In addition to implementing command line parsing in the main function and you will need to implement the translate_stream function

void translate_stream(FILE *stream, char *source, char *target, char *filter, int mode)

This function reads one line at a time from the stream and performs string translation based on the values in source and target. Any post processing is controlled by mode, which is a bitmask that specifies which filters to apply (ie. strip, reverse, lower, upper, startswith, endswith).

Note: You should apply the filters in the order specified above.

Hint: To handle the mode bitmask, you should have an enumerate for each filter, where each filter corresponds to a particular bit field:

enum {                        /* Define Modes */
    STRIP = 1<<1,
    ...
};

mode |= STRIP;                /* Set a Mode */

if (mode & STRIP) {           /* Check a Mode */
    ...
}

Task 3: `test_str.sh`

To test your str utility, you can use the provided test_str.sh script:

# Build artifacts
$ make

# Run test script manually
$ ./test_str.sh
Testing str utility...
 str -h                                   ... Success
 str -h (valgrind)                        ... Success
 str                                      ... Success
 str (valgrind)                           ... Success
 str aeio 4310                            ... Success
 str aeio 4310 (valgrind)                 ... Success
 str -s aeio 4310                         ... Success
 str -s aeio 4310 (valgrind)              ... Success
 str -r aeio 4310                         ... Success
 str -r aeio 4310 (valgrind)              ... Success
 str -l aeio 4310                         ... Success
 str -l aeio 4310 (valgrind)              ... Success
 str -u aeio 4310                         ... Success
 str -u aeio 4310 (valgrind)              ... Success
 str -t H3ll0 aeio 4310                   ... Success
 str -t H3ll0 aeio 4310 (valgrind)        ... Success
 str -d SP4C3 aeio 4310                   ... Success
 str -d SP4C3 aeio 4310 (valgrind)        ... Success
 str -l -u aeio 4310                      ... Success
 str -l -u aeio 4310 (valgrind)           ... Success
 str -r -u -t 0r3h aeio 4310              ... Success
 str -r -u -t 0r3h aeio 4310 (valgrind)   ... Success
   Score 3.00

Alternatively, you can both build the artifacts and run the test script by doing the following:

# Build and run test scripts
$ make test

Valgrind

The test_str.sh shell script will use the valgrind tool to verify that your program does not contain any memory errors such as memory leaks, uninitialized values, or invalid accesses.

You can run valgrind manually by doing:

$ echo "   Hello World" | valgrind --leak-check=full ./str-dynamic
==28627== Memcheck, a memory error detector
==28627== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==28627== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==28627== Command: ./str-dynamic
==28627==
  Hello World
==28627==
==28627== HEAP SUMMARY:
==28627==     in use at exit: 0 bytes in 0 blocks
==28627==   total heap usage: 2 allocs, 2 frees, 5,120 bytes allocated
==28627==
==28627== All heap blocks were freed -- no leaks are possible
==28627==
==28627== For counts of detected and suppressed errors, rerun with: -v
==28627== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Note: You should run valgrind on the dynamic executable rather than the static executable. Likewise, valgrind may behave differently on macOS than it does on Linux, so beware of spurious errors on the former.

Task 4: `README.md`

In your README.md, respond to the following prompts:

What is the difference between a static executable such as str-static and a dynamic executable such as str-dynamic?
Compare the sizes of str-static and str-dynamic, which one is larger? Why?
Login into a new shell and try to execute str-dynamic. Why doesn't str-dynamic work? Explain what you had to do in order for str-dynamic to actually run.
Login into a new shell and try to execute str-static. Why does str-static work, but str-dynamic does not in a brand new shell session?

Guru Point: Installfest (1 Point)

For extra credit, install a Linux distribution either on a partition on your laptop or in a virtual machine. Once you have Linux installed, please show your setup to the instructor or a TA to verify.

There are a number of Linux distributions and which one you wish to install is up to you. That said, these are probably the most popular ones:

You can find a more exhaustive list on Distrowatch. For virtualization software, Virtualbox is a popular choice.

Submission

To submit your assignment, please commit your work to the homework06 folder of your homework06 branch in your assignments GitLab repository. Your homework06 folder should only contain the following files:

Makefile
README.md
library.c
main.c
str.h
test_libstr.py
test_str.sh

Note: You need to commit the test scripts even though the Makefile automatically downloads them.

#--------------------------------------------------
# BE SURE TO DO THE PREPARATION STEPS IN ACTIVITY 0
#--------------------------------------------------

$ cd homework06                           # Go to Homework 06 directory
...
$ git add Makefile                        # Mark changes for commit
$ git add library.c                       # Mark changes for commit
$ git add str.h                           # Mark changes for commit
$ git add test-libstr.py                  # Mark changes for commit
$ git add README.md                       # Mark changes for commit
$ git commit -m "homework06: activity 1"  # Record changes
...
$ git add Makefile                        # Mark changes for commit
$ git add main.c                          # Mark changes for commit
$ git add test-str.sh                     # Mark changes for commit
$ git add README.md                       # Mark changes for commit
$ git commit -m "homework06: activity 2"  # Record changes
$ git push -u origin homework06           # Push branch to GitLab

Remember to create a merge request and assign the appropriate TA from the Reading 08 TA List.

Homework 06: Pointers, Arrays, Strings

Activity 0: Preparation

Activity 1: String Utilities Library (10 Points)

Starter Code

Task 0: str.h

Task 1: Makefile

Makefile Variables

Warnings

Task 2: library.c

Requirements

Task 3: test_libstr.py

Iterative Development

Task 4: README.md

Activity 2: Str Utility (5 Points)

Task 1: Makefile

Task 2: main.c

Task 3: test_str.sh

Valgrind

Task 4: README.md

Guru Point: Installfest (1 Point)

Submission

Task 0: `str.h`

Task 1: `Makefile`

Task 2: `library.c`

Task 3: `test_libstr.py`

Task 4: `README.md`

Task 1: `Makefile`

Task 2: `main.c`

Task 3: `test_str.sh`

Task 4: `README.md`