Program 1: Counted String Library
Programming assignments in CS 270 are individual work. You may discuss approaches with other students, but may not share code or pseudocode for the assignment. If do get ideas from somebody, or use snippets of code from elsewhere, you must cite the source in your README file.
For this assignment, you are explicitly permitted to share the disassembled code of test-full.o, should you and your classmates wish to work together to figure out exactly what the tests are doing.
Background
The built-in C string library (Links to an external site.)Links to an external site. uses null-terminated strings, where a “string” is simply (a pointer to) an array of characters, with the character ‘\0’ (NUL) marking the end of the string. While this is a convenient representation because a string parameter can be a simple primitive type (char * or const char *), it has several problems:
• Determining the length of a C string (with strlen() (Links to an external site.)Links to an external site.) is a linear-time operation: it must scan the array until it finds the first ‘\0’.
• C strings cannot contain the ‘\0’ character. That means a string cannot represent an arbitrary string of bytes, for example the contents of a binary file.
• C strings are difficult to use securely. For example, the documentation for strcat() (Links to an external site.)Links to an external site. says:
The behavior is undefined if the destination array is not large enough for the contents of both src and dest and the terminating null character.
Where “behavior is undefined” here really means that other parts of your program’s memory will be overwritten, giving the person who supplied the too-large string complete control over your program.
The most common alternative to null-terminated strings are so-called counted strings. A counted string stores both the data and its length. An example data structure for a counted string (similar to the one you will use in your program) would be:
struct kstring
{
char *data;
size_t length;
};
The C++
Your task
Your task is to implement a library (as a set of source and header files, documentation, and a Makefile) that provides a few useful functions for working with a counted string data structure. The definition of the data structure and prototypes for all the functions may be found in kstring.h. A set of function stubs, which you may use as the basis for your implementation, is provided in kstring-stubs.c.
Provided files
• Makefile for building the project.
• kstring.h: definition of the kstring structure, and prototypes for the functions you will implement.
• kstring-stubs.c: do-nothing stub implementations of the functions.
• test-abbrev.c: code for the test harness and 13 of the 26 test cases
• test-full.o: object file containing the test harness and all 26 test cases.
Specifications
Your library should implement the following eight functions. Prototypes for the functions, and the definition of the kstring struct (like a class, but with public data and no member functions), are in the provided kstring.h.
kstring kstralloc(size_t nbytes)
Creates and returns a new kstring object with the specified length. The .length member of the returned kstring should be equal to nbytes. The .data member should be a pointer to newly-allocated memory; the memory should be initialized by filling it with nbytes copies of the null byte (‘\0’). You can do so “by hand” or by using the memset() (Links to an external site.)Links to an external site. function
If there is an error allocating memory, this function should call abort() (Links to an external site.)Links to an external site..
Note: your program must support allocating (and subsequently using and freeing) zero-byte strings.
kstring kstrfrom(const char *cstr)
Creates and returns a new kstring object that contains a copy of the contents of a null-terminated C string, including the null terminator.
The .length member of the returned kstring should be the length of cstr, plus one for the null terminator. The .data member should be a pointer to newly-allocated memory (using , into which you have copied the contents of cstr, including the null byte at the end.
If there is an error allocating memory, this function should call abort().
void kstrfree(kstring str)
Frees the memory to which str.data points. Should correctly handle any kstring created with either kstralloc() or kstrfrom(), including those with length 0.
Note: Since the kstring is passed by value, setting its data pointer to NULL would not be reflected in the caller. This means that it is the caller’s responsibility not to re-use the kstring it passed to this function.
size_t kstrlen(kstring str)
Returns the length of the kstring str (that is, str.length).
char kstrget(kstring str, size_t pos)
Returns the character at index pos in str’s data.
If pos is out of bounds (greater than or equal to the length of str), this function should abort the program by calling abort().
void kstrput(kstring str, size_t pos, char ch)
Replaces the character at index pos in str’s data with the character ch.
If pos is out of bounds (greater than or equal to the length of str), this function should abort the program by calling abort().
void kstrextend(kstring *strp, size_t nbytes)
Modifies an existing kstring, pointed to by strp, to be at least nbytes bytes long.
If strp->length was already nbytes or longer, does nothing. That is, this function will never reduce the length of a string, only increase it.
If nbytes is longer than the current length, this function should take the following steps:
• Allocate a new array with the larger size.
• Copy data over from the old array to the new one.
• Free the old array.
• Fill the additional elements of the new array with null bytes (‘\0’).
• Make strp->data point to the new array.
• Set strp->length to the new size.
Note: if you are using malloc() for memory allocation, the function realloc() (Links to an external site.)Links to an external site. will take care of steps 1, 2, and 3 with a single function call.
If there is an error allocating memory, this function should call abort().
Note that this function takes a pointer to a kstring rather than taking a kstring by value. That means that changes you make to the strp->length and strp->data members will be visible to the caller.
void kstrcat(kstring *destp, kstring src)
Concatenates str onto the end of *destp. First extends *destp to be long enough to hold the contents of both strings, by calling kstrextend(). Then copies the contents of src into the dest
So, for example, if we execute the following code:
kstring a = kstrfrom(“hello”); // 6 bytes including \0
kstring b = kstrfrom(“world”); // 6 bytes including \0
kstrcat(&a, b);
Now a should have length 12, and the contents “hello\0world\0”.
Note that this function takes a pointer to the destination kstring. That means that changes you make to the destp->length and destp->data members will be visible to the caller.
Note: Remember to save the original length of *destp before calling kstrextend(). Otherwise, you won’t know where to copy src’s data to!
Constraints and technical restrictions
• Your library may be written in C, not C++. You may use any version of the C standard, but you must edit the Makefile to use the correct version flag in CFLAGS:
• -std=c89: old-school ANSI C (gcc default).
• -std=c99: the most commonly-used version of modern C.
• -std=c11: the most recent C standard.
• Your library should compile with the -Wall compiler flag (enable all warnings), without producing any compiler or linker warnings or errors.
• Your library must work with the provided kstring.h without modification.
• All dynamic memory allocation should use malloc, calloc, realloc, and free (Links to an external site.)Links to an external site..
• You may use the standard C string functions (strncpy, strlen, etc.). However, do keep in mind that they do not properly handle data containing null bytes, so it is probably a mistake to use them anywhere except kstrfrom() (which takes a null terminated string as its argument).
• It must be possible to link and run your library with the provided test-full.o on the class virtual machines.
• If memory allocation fails, and in certain other conditions, your program should abort by calling abort() (Links to an external site.)Links to an external site.. Simply exiting the program with exit() (Links to an external site.)Links to an external site. is not enough!
Test cases
Two test suites are provided for your program. The first, test-abbrev.c, contains thirteen functions, each implementing a test cases, as well as a main() that runs all the tests and tallies the number of successes (the function returns a positive number), failures (the function returns zero), and skipped tests (the function returns a negative number). You are welcome to modify this file, for example to add your own test cases.
The second test suite is provided as an object file, test-full.o. This test suite is similar to test-abbrev, but includes thirteen additional test cases, for a total of twenty-six. Source code is not provided for the additional tests, and you may not modify this file (though you are welcome to reverse-engineer it if you’d like).
A Makefile is provided that will build both test programs, given an object file kstring.o. It will also compile kstring.o from a file named kstring.c.
Grading will be based in part on the performance of your library under the test-full suite. Your program should pass all twenty-six tests. Note that, if your library causes a test case to crash, you are considered to have failed that test and all the subsequent tests. The three test cases that expect your library to abort are constructed so that aborting does not terminate the test program itself.
The twenty-six test cases in test-full are as follows. The ones marked with an asterisk (*) also appear, with source code, in test-abbrev.c.
• * kstralloc + kstrfree (simply checks that calling the two functions properly does not crash)
• * kstralloc initializes memory to 0
• * kstralloc sets length
• kstralloc sets length (big)
• * kstralloc sets length (0 bytes)
• kstralloc aborts on allocation failure (expected to abort)
• * kstrlen matches allocation
• kstrlen matches allocation (big)
• kstrlen matches allocation (0 bytes)
• * kstrfrom gives correct length
• * kstrfrom contains null byte
• kstrfrom contains correct data
• kstrfrom copies, not shares, data
• * kstrget fetches all indices correctly
• kstrget aborts when out of bounds (expected to abort)
• * kstrput sets all indices correctly
• kstrput aborts when out of bounds (expected to abort)
• * kstrextend lengthens kstring
• * kstrextend does not shorten kstring
• kstrextend supports length-0 kstring
• kstrextend copies old contents
• kstrextend extends with null bytes
• kstrcat of two empty kstrings (“empty” here means length zero)
• * kstrcat with empty kstring (second argument is empty)
• kstrcat onto empty kstring (first argument is empty)
• * kstrcat has correct data (neither argument is empty)
Memory safety
The test suites should execute without any memory leaks, crashes, out-of-bounds memory accesses, or incorrectly freed memory (freeing the same memory twice, or attempting to free memory that was not dynamically allocated).
To test your program for memory errors, you can use valgrind :
valgrind –tool=memcheck –child-silent-after-fork=yes ./test-full
A Makefile rule is provided to run this command for you: make memcheck. Near the end of the output you want to see:
==22657== HEAP SUMMARY:
==22657== in use at exit: 0 bytes in 0 blocks
…
==22657== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
You may find it helpful to consult the Valgrind manual (Links to an external site.)Links to an external site., especially the Quick Start Guide at the beginning.
Note: It is acceptible for your program to leak memory when it aborts; the three relevant test cases already take that possibility into account.
Documentation
Your submission should include a README file. This should be a plain text file with at least the following sections:
• Author: Your name and email address, and the date the program was finished.
• Contents: A list of all the files in your submission, with a brief one-line description of each. For example, “kstring.c: implementation of kstring functions”, or “README: this file”.
• Running: Brief instructions explaining how to compile and run your program.
• Implementation notes: Describe any design decisions you made when implementing your functions. For example: which method do they use to allocate memory, how do you detect and handle errors, and did you implement any additional helper functions?
• Limitations: If you have any failing test cases, memory leaks, or other memory errors, describe the problems here. Where do the problems occur, what steps did you take to try to solve them, and what further steps would you take if you had more time?
Likewise, if you noticed in your own testing any situations that your library does not handle well, even if they are not covered by the test cases, describe them here.
• References: If you discussed the design of your program with anyone, list them here and describe their contribution. For example:
The design of the frobulate() function benefitted from discussions with my tutor J. Random Hacker, who suggested doing the bit-twiddling before the loop rather than inside the loop.
Likewise, if you used code snippets from sites such as Stack Overflow, describe what you used, explain how it works in your own words, and provide the name of the author and the URL where they posted the code. For example:
The data-copying loop in perform_magic() is based on code written by C. Guru at: http://answermyprogrammingquestions.com/0xc0debeef/. The loop casts the character pointer to a integer pointer and uses that to copy four bytes of data at a time. If the number of bytes was not divisible by four, the code then copies the remaining 1-3 bytes individually.
Programming assignments are expected to be your own work, so any borrowed code should be very small relative to the total size of your program. You may not borrow code from or share code with other UK students at all.
What to submit
Submit a zip or tar.gz file containing a directory with the following files:
• The source code for your implementation of the kstring library.
• A Makefile that builds a test-full excecutable combining the test suite in test-full.o with your kstring library. This may be the provided Makefile, a modified version of it, or a brand new Makefile.
• A plain text README file as described in “Documentation” above.
• A typescript (a terminal log produced by the program script) named script.txt, that shows the process of building and executing your test program on the class VM.
To make a .tar.gz archive of the directory program1, you can use a command like:
tar czvf cs270-program1.tar.gz program1/
To make a .zip archive:
zip -r cs270-program1.zip program1/
Submit your .tar.gz or .zip file to this assignment.
Grading
This assignment will be scored out of 100 points:
• 52 points: 2 points per test case passed. Remember that if the test program crashes, all subsequent tests are considered to have failed.
• 15 points: program compiles with no warnings under -Wall.
• 15 points: the test cases run without any memory errors or memory leaks, as reported by valgrind. See section “Memory safety” above.
• 9 points: documentation is complete, readable, and error-free.
• 9 points: code shows good style (Links to an external site.)Links to an external site. (variable names, formatting, error handling, etc). This includes comments!
Hints and FAQs
• I would recommend implementing your functions in the order they appear in the test cases. First get the second test to pass without crashing, then the third test, then the fourth, and so on.
• Be sure to use valgrind to check your program for memory leaks and array bounds exceptions. See section “Memory safety” above.
• My implementation of kstring.c came out to around 90 lines not including comments. Yours may be shorter or longer of course, but if it gets to be more than a few hundred lines, you may be making the task more complicated than it needs to be.
PreviousNext