Homework 06: Arrays, Pointers, Strings

The goal of this homework assignment is to allow you to practice using arrays, pointers, 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 translate program 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 11:59 PM Friday, March 24, 2017.

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, libstringutils.so, which contains functions such as string_lowercase and string_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:

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

# Download starter code tarball
$ curl -O http://www3.nd.edu/~pbui/teaching/cse.20289.sp17/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
    \_ stringutils.c              # This is the C99 implementation file for the string utilities library
    \_ stringutils.h              # This is the C99 header file for the string utilities library
    \_ test_stringutils.py        # This is the Python test script for the string utilities library
    \_ test_translate.py          # This is the Python test script for the translate tool
    \_ translate.c                # This is the C99 implementation file for the translate tool

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

Task 0: `stringutils.h`

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

/* stringutils.h: String Utilities */

#ifndef STRINGUTILS_H
#define STRINGUTILS_H

#include <stdbool.h>

/* Case */
char *  string_lowercase(char *s);
char *  string_uppercase(char *s);

/* Comparison */
bool  string_startswith(char *s, char *t);
bool  string_endswith(char *s, char *t);

/* Strip */
char *  string_chomp(char *s);
char *  string_strip(char *s);

/* Reverse */
char *  string_reverse(char *s);
char *  string_reverse_words(char *s);

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

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

#endif

/* 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.

For this task, you do not need to modify the 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. libstringutils.a, libstringutils.so, etc.):

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

TARGETS=  libstringutils.a \
          libstringutils.so

all:    $(TARGETS)

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

test:     test-libstringutils

test-libstringutils:  libstringutils.so test_stringutils.py
          ./test_stringutils.py -v

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

For this task, you will need to add rules for building the static library libstringutils.a and the shared library libstringutils.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.

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 stringutils.o stringutils.c
ar rcs libstringutils.a stringutils.o
gcc -L. -shared -o libstringutils.so stringutils.o

# Run all tests
$ make test
./test_stringutils.py -v
test_00_string_lowercase (__main__.StringUtils) ... ok
test_01_string_uppercase (__main__.StringUtils) ... ok
test_02_string_startswith (__main__.StringUtils) ... ok
test_03_string_endswith (__main__.StringUtils) ... ok
test_04_string_chomp (__main__.StringUtils) ... ok
test_05_string_strip (__main__.StringUtils) ... ok
test_06_string_reverse (__main__.StringUtils) ... ok
test_07_string_reverse_words (__main__.StringUtils) ... ok
test_08_string_translate (__main__.StringUtils) ... ok
test_09_string_to_integer (__main__.StringUtils) ... ok

----------------------------------------------------------------------
Ran 10 tests in 0.000s

OK

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

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

Task 2: `stringutils.c`

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

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

char * string_lowercase(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 * string_uppercase(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 string_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 string_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 * string_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 * string_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 * string_reverse_range(char *from, char *to)

This internal function reverses the letters in the substring specified by from and to (e.g. s[from:to:-1] in Python).

Hint: Considering how to swap two chars.
char * string_reverse(char *s)

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

Hint: Use the internal string_reverse_range function.
char * string_reverse_words(char *s)

This function reverses the words in s (e.g. somewhat like ' '.join(s.split()[::-1]) in Python).

Hint: Use the internal string_reverse_range function to reverse the string and then the individual words.
char * string_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 string_to_integer(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.

Pointers Only

When accessing or iterating through strings, you may only use pointers. That is you cannot index into a string.

Allowed:

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

Not Allowed:

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

Task 3: `test_stringutils.py`

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

# Build artifacts
$ make

# Run test script manually
$ ./test_stringutils.py -v
test_00_string_lowercase (__main__.StringUtils) ... ok
test_01_string_uppercase (__main__.StringUtils) ... ok
test_02_string_startswith (__main__.StringUtils) ... ok
test_03_string_endswith (__main__.StringUtils) ... ok
test_04_string_chomp (__main__.StringUtils) ... ok
test_05_string_strip (__main__.StringUtils) ... ok
test_06_string_reverse (__main__.StringUtils) ... ok
test_07_string_reverse_words (__main__.StringUtils) ... ok
test_08_string_translate (__main__.StringUtils) ... ok
test_09_string_to_integer (__main__.StringUtils) ... ok

----------------------------------------------------------------------
Ran 10 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
>>> stringutils = ctypes.CDLL('./libstringutils.so')

# Set return type for string_lowercase
>>> stringutils.string_lowercase.restype = ctypes.c_char_p

# Call string_lowercase function
>>> stringutils.string_lowercase('Hello, World!')
'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:

Describe how your string_reverse_words function works and analyze its time complexity and space complexity in terms of Big-O notation.
Describe how your string_translate function works and analyze its time complexity and space complexity in terms of Big-O notation.
Describe how your string_to_integer function works and analyze its time complexity and space complexity in terms of Big-O notation.
What is the difference between a shared library such as libstringutils.so and a static library such as libstringutils.a?
- Comparing the sizes of libstringutils.a and libstringutils.so, which one is larger? Why?

Activity 2: Translate (5 Points)

Once you have a working string utilities library, you are to complete the translate.c program:

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

Post Translation filters:

   -s     Strip whitespace
   -r     Reverse line
   -w     Reverse words in line
   -l     Convert to lowercase
   -u     Convert to uppercase

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

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

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

# Reverse words
$ echo "   Hello World" | ./translate-static -w
World Hello

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

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

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

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

The translate.c program must use the corresponding functions from the string utilities library 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:

translate-static: This is a static executable of translate.c.
translate-dynamic: This is a dynamic executable of translate.c.
test-translate: This is a PHONY rule for running the test_translate.py script.

Once again, be sure to add any rules for any intermediate object files. Additionally, be sure to add translate-static and translate-dynamic to the all recipe and to add test-translate to the test 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 stringutils.o stringutils.c
ar rcs libstringutils.a stringutils.o
gcc -L. -shared -o libstringutils.so stringutils.o
gcc -g -gdwarf-2 -Wall -std=gnu99 -c -o translate.o translate.c
gcc -L. -o translate-dynamic translate.o -lstringutils
gcc -L. -static -o translate-static translate.o -lstringutils

# Run all tests
$ make test
./test_stringutils.py -v
test_00_string_lowercase (__main__.StringUtils) ... ok
test_01_string_uppercase (__main__.StringUtils) ... ok
test_02_string_startswith (__main__.StringUtils) ... ok
test_03_string_endswith (__main__.StringUtils) ... ok
test_04_string_chomp (__main__.StringUtils) ... ok
test_05_string_strip (__main__.StringUtils) ... ok
test_06_string_reverse (__main__.StringUtils) ... ok
test_07_string_reverse_words (__main__.StringUtils) ... ok
test_08_string_translate (__main__.StringUtils) ... ok
test_09_string_to_integer (__main__.StringUtils) ... ok

----------------------------------------------------------------------
Ran 10 tests in 0.001s

OK
./test_translate.py -v
test_00_echo (__main__.Translate) ... ok
test_00_echo_valgrind (__main__.Translate) ... ok
test_01_translate (__main__.Translate) ... ok
test_01_translate_valgrind (__main__.Translate) ... ok
test_02_strip (__main__.Translate) ... ok
test_02_strip_valgrind (__main__.Translate) ... ok
test_03_reverse (__main__.Translate) ... ok
test_03_reverse_valgrind (__main__.Translate) ... ok
test_04_reverse_words (__main__.Translate) ... ok
test_04_reverse_words_valgrind (__main__.Translate) ... ok
test_05_lowercase (__main__.Translate) ... ok
test_05_lowercase_valgrind (__main__.Translate) ... ok
test_06_uppercase (__main__.Translate) ... ok
test_06_uppercase_valgrind (__main__.Translate) ... ok

----------------------------------------------------------------------
Ran 14 tests in 9.751s

OK

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

Task 2: `translate.c`

The translate.c file is contains the C99 implementation of the string translation tool described above:

/* translate.c: string translator */

#include "stringutils.h"

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

/* Globals */

char *PROGRAM_NAME = NULL;

/* 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, "   -w     Reverse words in line\n");
    fprintf(stderr, "   -l     Convert to lowercase\n");
    fprintf(stderr, "   -u     Convert to uppercase\n");
    exit(status);
}

void translate_stream(FILE *stream, char *source, char *target, int mode) {
    /* TODO */
}

/* Main Execution */

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

    /* 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, 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, reverse words, lowercase, uppercase).

Note: You should apply the filters in the order specified above. Mixing lowercase and uppercase leads to undefined behavior.

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

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

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

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

Task 3: `test_translate.py`

To test your translate.c program, you can use the provided test_translate.py script:

# Build artifacts
$ make

# Run test script manually
$ ./test_translate.py -v
test_00_echo (__main__.Translate) ... ok
test_00_echo_valgrind (__main__.Translate) ... ok
test_01_translate (__main__.Translate) ... ok
test_01_translate_valgrind (__main__.Translate) ... ok
test_02_strip (__main__.Translate) ... ok
test_02_strip_valgrind (__main__.Translate) ... ok
test_03_reverse (__main__.Translate) ... ok
test_03_reverse_valgrind (__main__.Translate) ... ok
test_04_reverse_words (__main__.Translate) ... ok
test_04_reverse_words_valgrind (__main__.Translate) ... ok
test_05_lowercase (__main__.Translate) ... ok
test_05_lowercase_valgrind (__main__.Translate) ... ok
test_06_uppercase (__main__.Translate) ... ok
test_06_uppercase_valgrind (__main__.Translate) ... ok

----------------------------------------------------------------------
Ran 14 tests in 9.751s

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_translate.py Python 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 ./translate-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: ./translate-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:

Describe how the translate.c program works. In particular, explain:
- How you implemented command line parsing.
- How you implemented the translation.
- How you implemented the different post processing filters.
Be sure to describe how you used and handled the mode bitmask.
What is the difference between a static executable such as translate-static and a dynamic executable such as translate-dynamic?
- Comparing the sizes of translate-static and translate-dynamic, which one is larger? Why?
- When trying to execute translate-static, does it work? If not, explain what you had to do in order for it to actually run.
- When trying to execute translate-dynamic, does it work? If not, explain what you had to do in order for it to actually run.

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 in your assignments GitLab repository. Your homework06 folder should only contain at the following files:

Makefile
README.md
stringutils.c
stringutils.h
translate.c
test_stringutils.py
test_translate.py

Homework 06: Arrays, Pointers, Strings

Activity 1: String Utilities Library (10 Points)

Starter Code

Task 0: stringutils.h

Task 1: Makefile

Makefile Variables

Task 2: stringutils.c

Pointers Only

Task 3: test_stringutils.py

Iterative Development

Task 4: README.md

Activity 2: Translate (5 Points)

Task 1: Makefile

Task 2: translate.c

Task 3: test_translate.py

Valgrind

Task 4: README.md

Guru Point: Installfest (1 Point)

Submission

Task 0: `stringutils.h`

Task 1: `Makefile`

Task 2: `stringutils.c`

Task 3: `test_stringutils.py`

Task 4: `README.md`

Task 1: `Makefile`

Task 2: `translate.c`

Task 3: `test_translate.py`

Task 4: `README.md`