KAIST
EE209: Programming Structures for EE

Purpose

The purpose of this assignment is to help you learn/review (1) arrays and pointers in the C programming language, (2) how to create and use stateless modules in C, (3) the "design by contract" style of programming, and (4) how to use the GNU/UNIX programming tools, especially bash, vscode (or any other editor of your choice), gcc, and gdb.

Rules

Implement the string functions listed by the Table in Part 1. and Part 2 is implementing 'Simple Grep', which is worth 50% of this assignment.

You will get an extra 10% of the full score if you implement the Part 1 only with pointer notation when you access the character. See the Extra credit section below (Extra Credit for Part 1).

Background

As you know, the C programming environment provides a standard library. The facilities provided in the standard library are declared in header files. One of those header files is string.h; it contains the declarations of "string functions," that is, functions that perform operations on character strings. Appendix D of the King textbook, Appendix B3 of the Kernighan and Ritchie textbook, and the UNIX "man" pages describe the string functions. The string functions are used heavily in programming systems; certainly any editor, compiler, assembler, or operating system created with the C programming language would use them.

Overview of Your Task

Your task in this assignment is to use C to create the "Str" module that provides string manipulation functions. Specifically, design your Str module so that each function behaves the same as described below. Your task in this assignment is twofold.

[Part 1] Read the description of the basic string library functions carefully, and implement each function. The basic functions are most commonly used standard string functions. Each function should behave the same as its corresponding standard C function.

[Part 2] Implement a simplified version of grep using Str functions. Read the provided file that contains skeleton code carefully, edit the file to make it process the required functionality.

Part 1: The Basic Str Function Implementation

Your task for the first part is to use C to implement seven basic string manipulation functions: StrCopy(), StrCompare(), StrFindChr(), StrFindStr(), StrConcat(), StrToLong(), and StrCaseCompare(). Those seven functions should follow the format of the corresponding standard C library functions. You can easily find the function's description and operation in the UNIX "man" page.

The following table shows the required basic string functions in Part 1 and their corresponding function names in the standard C library.

Use the Str module's interface in a file named str.h, and place your Str function definitions in str.c.

Note that your Str functions should not call any of the standard string functions. In the context of this assignment, pretend that the standard string functions do not exist. However, your functions may call each other, and you may define additional (non-interface) functions.

Design each function definition so it calls the assert macro to validate the function's parameters. In that way, your Str functions should differ from the standard C string functions. Specifically, design each function definition to assert that each string parameter is not NULL except for the second argument of StrToLong, which could be NULL by the specification. See the note below for more information of the assert() macro function.

Beware of type mismatches. In particular, beware of the difference between type size_t and type int: a variable of type size_t can store larger integers than a variable of type int can. Your functions should (in principle) be able to handle strings whose lengths exceed the capacity of type int. Also beware of type mismatches related to the use of the const keyword.

Assume the third parameter in StrToLong() is always 10 (base == 10). Otherwise, the function should simply returns 0. Also, the function does not have to set errno in case of an error, but the return value must be identical as that of strtol() even in the case of an error (e.g., 0, LONG_MIN, LONG_MAX). Use #include <limits.h> to use LONG_MIN and LONG_MAX in your code. BTW, you should not use a similar function like atoi(), atol(), ... to implement this function.

Some hints on implementation of StrToLong()

1. How to skip spaces?

Use isspace() to check if the current character is one of spaces. For example, while (*p && isspace(*p)) p++; would move p to point to a non-space character in the string, assuming p initially points to the input string. For each character, make sure to check if *p is not '\0' (or simply 0). If p points to a null charater, you have reached the end of the string.

2. How to convert a number string to an int value?

Refer to the following code. p points to a number string, and x is the current result (with initial value of 0). For each digit, you need to multiply x with 10 and add the digit to x.

  int x = 0;
  char *p = "3456";
  int temp;

  while (*p && isdigit(*p)) {
     temp = *p - '0';
      x = 10 * x + temp;
     p++;
  }
  printf("number =%d\n", x); // it will print out 3456
  

Extra Credit for Part 1: Implement functions with pointer notation

There are various ways to implement the functions in Part 1. Especially, you can access the character by pointer dereferencing like *pcSrc or by using an array notation such as pcSrc[uiLength] .

Here are two examples of StrGetLength() implementation. The first code implements the StrGetLength() function with the array notation; it traverses each given string or accesses the character using an index relative to the beginning of the string. However, with the pointer notation, the second version traverses each given string using an incremented pointer.

size_t StrGetLength(const char pcSrc[]) /* Use array notation */
{
   size_t uiLength = 0U;
   assert(pcSrc != NULL);
   while (pcSrc[uiLength] != '\0')
      uiLength++;
   return uiLength;
}

size_t StrGetLength(const char *pcSrc) /* Use pointer notation */
{
   const char *pcEnd;
   assert(pcSrc != NULL);
   pcEnd = pcSrc;
   while (*pcEnd != '\0') /* note that *(pcSrc + uiLength) is valid but is "NOT" acceptable as pointer notation */
      pcEnd++;
   return (size_t)(pcEnd - pcSrc);
}

You can freely implement Part 1. However, if you implement part 1 only with pointer notation, you can get extra 10% of the full score. Please write your choice of implementation in the readme file. That is, specify if you used only the pointer notation for Part 1 in the readme file.

Test your Str Functions

We provide a test client (client.c) that compares the results of the Str and C standard library functions with various input. Please use this code for testing and debugging. You can compile the test client with gcc209 as follows.

gcc209 -o client client.c str.c

./client StrCopy

./client [StrGetLength|StrCopy|StrCompare|StrFindStr|StrConcat|StrFindChr|StrToLong|StrCaseCompare]

Note that passing all tests provided by the client does not mean that your function always behaves correctly. Please devise your own testing (e.g., by changing the client code) for more confidence. Note that we may use a different test client for grading.

Part 2: Simple Grep

grep is a popular UNIX tool that manipulates input strings. In this part, you implement a simplified version of grep called sgrep. sgrep searches for a given pattern in each line from stdin, and prints out the line to stdout if it matches the pattern.

./sgrep [pattern]

pattern can be a simple string (e.g., 'hello', 'kaist') or it can inlcude one or more '*' in the string. '*' matches zero or more repetition of any character (except one character ('\n')). For example, 'ka*is*t' can be matched with 'kaist', 'kaxxist', or 'kaaaisss ?kkt'.

Here are some usage examples of sgrep (you can also see the test files (google.txt and microsoft.txt) which are used in the following example):

$ ./sgrep "*og*e" < google.txt
Google Inc. is an American multinational technology company specializing
advertising technologies, search, cloud computing, and software.[5]
Google was founded by Larry Page and Sergey Brin while they were Ph.D.
students at Stanford University. Together, they own about 14 percent of
 supervoting stock. They incorporated Google as a privately held company on
 be evil".[9][10] In 2004, Google moved to its new headquarters in Mountain
View, California, nicknamed the Googleplex.[11] In August 2015, Google
Alphabet Inc. When this restructuring took place on October 2, 2015, Google
became Alphabet's leading subsidiary, as well as the parent for Google's

$ ./sgrep "s*t" < microsoft.txt
Microsoft Inc. is an American multinational technology company specializing
in Internet-related services and products. These include online
advertising technologies, search, cloud computing, and software.[5]
Most of its profits are derived from AdWords,[6][7] an online advertising
service that places advertising near the list of search results.
Microsoft was founded by Larry Page and Sergey Brin while they were Ph.D.
students at Stanford University. Together, they own about 14 percent of
its shares and control 56 percent of the stockholder voting power through
 supervoting stock. They incorporated Microsoft as a privately held company on
An initial public offering followed on August 19, 2004.
Its mission statement from the outset was "to organize the world's
and its unofficial slogan was "Don't
 be evil".[9][10] In 2004, Microsoft moved to its new headquarters in Mountain
View, California, nicknamed the Microsoftplex.[11] In August 2015, Microsoft
announced plans to reorganize its interests as a holding company called
Alphabet Inc. When this restructuring took place on October 2, 2015, Microsoft
became Alphabet's leading subsidiary, as well as the parent for Microsoft's
Internet interests.[12][13][14][15][16]

$ ./sgrep "s t" < microsoft.txt
announced plans to reorganize its interests as a holding company called
became Alphabet's leading subsidiary, as well as the parent for Microsoft's

Rules:

• Use your Str functions to implement the functionality. That is, you need to finish Part 1 first to get any credit for this task. You should not use any string function in string.h
• Assume each line (including a new line character ('\n') is no more than 1023 bytes. You should stop your program with a proper error message("Error: input line is too long\n") if you encounter a line larger than 1023 bytes.
• A pattern argument refers to a sequence of any characters that may contain spaces or '*'. In case it contains spaces or '*', it must be enclosed with double quote (") characters (e.g., "hello world", "s*t"). The pattern can be empty (""), and an empty pattern matches any line. No need to handle an escape character in the pattern string for this assignment.
• Assume a pattern string no more than 1023 bytes. You should stop your program with a proper error message("Error: pattern is too long\n") if you encounter a command-line argument that is too long.
• Any error message should be printed out to standard error (stderr). Use fprintf(stderr, ...) for that.
• Unlike Part 1, you don't have to add assert function while implementing sgrep. In other words, after printing out the error messages in error case, sgrep should be finished with EXIT_FAILURE as the return value. Details are written in skeleton code, so please read the comments in skeletion code (sgrep.c).

Tips:

• We provide a skeleton code file (sgrep.c). You can start with the file.
• fgets should be useful for reading a line from a file. 'man fgets' should give you more information.
• You are free to choose whatever implementation strategy, but we suggest using a recursive function for implementing '*'. In fact, it will require less then 20 lines of code to implement '*' with a recursive function. Well, a higher performance implementation should use another technique, but that's not necessary for this assignment. We won't penalize for low performance unless it's really slow (e.g., seconds of delay for a short text).

Test your sgrep Function

We provide the test files in the tests directory. After compiling your code, test your pragram using: find01.sh, find02.sh, find03.sh, find08.sh, and find09.sh. The example commandlines are provided below.

$ chmod +x ./tests/input/find01.sh
$ ./tests/input/find01.sh >stdout 2>stderr
$ diff ./tests/answer/find01.stdout stdout
$ diff ./tests/answer/find01.stderr stderr

If your program is working fine, nothing will be printed out after the diff command.

Logistics

Develop on lab machines using vscode (or any other editor of your choice) to create source code and gdb to debug.

For part 1, you implement the code str.c, which should contain the definitions of required functions.

For part 2, a skeleton C file is available here: sgrep.c. It implements the basic I/O and argument parsing, so all you need is fill out the rest of the functionalities with Str functions. Feel free to use this file as your starting point (of course, you don't have to use it), and change any part in the code if you'd like.

Create a readme text file that contains:

• Your name and your student ID
• A description of whatever help (if any) you received from others while doing the assignment, and the names of any individuals with whom you collaborated, as prescribed by the course "Policy" web page.
• Is it possible for StrCopy to call assert to verify that the destination memory area specified by the caller is large enough? Explain.
• (Optionally) Please write the your implementation method in readme text file whether you use pointer notation for the extra credit.
• (Optionally) An indication of how much time you spent doing the assignment.
• (Optionally) Your assessment of the assignment.
• (Optionally) Any information that will help us to grade your work in the most favorable light. In particular you should describe all known bugs.

Submission

Use KLMS submission link to submit your assignments. Your submission should be one gzipped tar file whose name is YourStudentID_assign2.tar.gz . For example, if your student ID is 20241234, please name the file as 20241234_assign2.tar.gz.

Your submission file need to include the following files:

• (Task 1) updated str.c file
• (Task 2) updated sgrep.c file
• readme text file
• Observance of Ethics. Sign on the document, save it into a PDF file, and submit it.

In order to create a gzipped tar file, (1) put readme and EthicsOath.pdf into the current directory where your str.c and sgrep.c exist, (2) change the STUDENT_ID with yours, and (3) run the following command:

$ make submit

If you complete all steps, YourStudentID_assign2.tar.gz will be created.

Finally, your submission file should look like this:

gcc209 -D NDEBUG sgrep.c str.c -o sgrep

size_t StrGetLength(const char pcSrc[])
{
   size_t uiLength = 0U;
   assert(pcSrc); /* NULL address, 0, and FALSE are identical. */
   while (pcSrc[uiLength]) /* null character and FALSE are identical. */
      uiLength++;
   return uiLength;
}

size_t StrGetLength(const char *pcSrc)
{
   const char *pcEnd;
   assert(pcSrc); /* NULL address, 0, and FALSE are identical. */
   pcEnd = pcSrc;
   while (*pcEnd) /* null character and FALSE are identical. */
      pcEnd++;
   return (size_t)(pcEnd - pcSrc);
}

char *StrFindStr(char *pcHaystack, char *pcNeedle)
{
   ...
}

const char *pcBig = "hello";
const char *pcSmall = "lo";
 ...
 ... StrFindStr(pcBig, pcSmall) ...
 ...

const char *StrFindStr(const char *pcHaystack, const char *pcNeedle)
{
   ...
}

char *pcBig = "hello";
char *pcSmall = "lo";
char *pc;
 ...
pc = StrFindStr(pcBig, pcSmall);
 ...

char *StrFindStr(const char *pcHaystack, const char *pcNeedle)
{
   ...
   pc = pcHaystack;
   ...
   /* Increment pc so it points to the appropriate character. */
   ...
   return pc;
}

return (char*)pc;