Assignment 5: Give a little bit

Due Wednesday, Feb 23, before midnight

The goals for this assignment are:

  • Work with 2D arrays

  • Use malloc and free

  • Read and write binary files

All programs must run without memory errors and leaks!

Install the VS Code extension, "PBM/PPM/PGM Viewer" by ngtystr, so you can easily view your PPM files!

Update your repository

Do a fetch upstream to obtain the basecode for this assignment.

Using the command line

  • Open terminal and change your current directory to your assignment repository.

  • Run the command git fetch upstream

  • Run the command git merge upstream/main

Your repository should now contain a new folder named A05.

The fetch and merge commands update your repository with any changes from the original.

Update your repository

Do a fetch upstream to obtain the basecode for this assignment.

Using the command line

  • Open terminal and change your current directory to your assignment repository.

  • Run the command git fetch upstream

  • Run the command git merge upstream/master

Your repository should now contain a new folder named A02.

The fetch and merge commands update your repository with any changes from the original.

1. Crossword

Implement a program, crossword.c, that generates a crossword using two words from a user. Your program should create a 2D array of characters to hold your crossword puzzle. Your algorithm should identify a common letter between the given words and list one word vertically and the other word horizontally. If there is no common letter, print a message and quit.

$ make crossword
gcc -g -Wall -Wvla -Werror crossword.c -o crossword
$ ./crossword
Usage: ./crossword  
$ ./crossword elephant onion
. e . . .
. l . . .
. e . . .
. p . . .
. h . . .
. a . . .
o n i o n
. t . . .
$ ./crossword elephant zoo
No common letter!

Requirements/Hints:

  • You must store the crossword in a dynamically allocated array.

  • Use malloc and free to allocate a 2D array to store the grid.

  • Your program must use command line arguments!

  • Your program should print the results so that the words are properly aligned.

  • For extra challenge, try to support more than two words!

To read in command line arguments, define main with argc and argv parameters as follows. The first command line argument is always the program name. argc is the number of arguments. You can use atoi and atof to convert from strings to numeric types (int and float respectively) 
int main(int argc, char* argv[]) {
    if (argc < 3) {
    printf("Usage: %s <word1> <word2>\n", argv[0]);
    exit(0);
  }
  // todo: your code here
  return 0;
}

2. PPM

Implement two functions, read_ppm and write_ppm, that read and write binary PPM files. This functions are implemented in the file load_ppm.h and tested using code in test_ppm.c.

2.1. Background

PPM (Portable Pix Map) is an image file format that stores the colors of an image as a 2D array of colors. Each color is represented as a RGB triplet, representing red, green and blue respectively. The properties of the image, such as its size and color format, are specified at the start of the file (called its "header information"). PPM supports both ASCII (plain text) and binary data (raw).

We will write a funtion that reads PPM files in binary format!

For example, consider the following image

example5000

The above image contains a 4x4 grid of colored pixels. Each pixel is a triplet of red-blue-green (RGB) color values, each stored as an unsigned char. Unsigned chars have values which range from 0 to 255, where smaller values correspond to darker colors. The triplet (0,0,0) corresponds to black. The triplet (255,255,255) cooresponds to white. The triplet (255,0,0) corresponds to red. This system of colors is called the RGB Color Model and it is a common standard for representing colors on a computer.

The RGB colors for the pixels in the above image are as follows

(0,0,0)      (100,0,0)    (0,0,0)     (255,0,255)
(0,0,0)      (0,255,175)  (0,0,0)     (0,0,0)
(0,0,0)      (0,0,0)      (0,15,175)  (0,0,0)
(255,0,255)  (0,0,0)      (0,0,0)     (255,255,255)

In binary format (also called raw format), the image is stored as follows. To see for yourself, do hexedit feep-raw.ppm.

00000000   50 36 0A 23  20 43 72 65  61 74 65 64  20 62 79 20  47 49 4D 50  20 76 65 72  P6.# Created by GIMP ver
00000018   73 69 6F 6E  20 32 2E 31  30 2E 32 34  20 50 4E 4D  20 70 6C 75  67 2D 69 6E  sion 2.10.24 PNM plug-in
00000030   0A 34 20 34  0A 32 35 35  0A 00 00 00  64 00 00 00  00 00 FF 00  FF 00 00 00  .4 4.255....d...........
00000048   00 FF AF 00  00 00 00 00  00 00 00 00  00 00 00 00  0F AF 00 00  00 FF 00 FF  ........................
00000060   00 00 00 00  00 00 FF FF  FF                                                  .........

The leftmost column is byte number in hexidecimal. For example, 0x18 is 24 in decimal. There are 24 bytes on the first row on output. The rightmost column displays the raw data in ASCII, using . for non-visible ASCII codes, such as '\0' and 'Escape'.

Regardless of format, every PPM file starts the following information in its header.

  • A "magic number" indicating the type of PPM. Binary types start with "P6".

  • Whitespace (blanks, tabs, \n, \r, etc)

  • Width and height as ASCII decimal integers (separated by whitespace)

  • Maximum color value as an ASCII decimal integer. You can assume the Maxval is less than 256, meaning each RGB value is 1 byte.

  • A single whitespace character

  • A raster (e.g. the array of pixels) of Height number of rows and Width number of columns, in order from top to bottom.

PPM images may contain comments in their header. These must be on their own line and start with the symbol #.

The header information is always in plain text. It is only the pixel data that differs between ASCII and raw formats.
PPM files can be viewed using tools such as Photoshop and Gimp.

2.2. Read PPM

For this question, you will implement a function, read_ppm(), that can read PPM files stored in binary format. This function should take a filename as input and return a 2D array of struct pixel. A struct pixel has the following definition

struct ppm_pixel {
    unsigned char red;
    unsigned char green;
    unsigned char blue;
};

The user of the function read_ppm is reponsible for freeing the memory allocated by this function.

You will re-use this function throughout the semester. For this reason, we place its implementation in it’s own file, read_ppm.c, and use a header file, read_ppm.h, to include it in our main application.

You may implement your 2D array of pixels as either a flat array or an array or arrays. For example, if you return a flat array, your function should be defined as struct ppm_pixel* read_ppm(const char* filename, int* width, int* height). If you return an array or arrays, your function should be defined as struct ppm_pixel** read_ppm(const char* filename, int* width, int* height). In both cases, use the parameters width and height to return the width and height of the image.

In the file, test_read.c, write a short test that calls your function and prints the contents of feep-raw.ppm like so:

$ make test_read
gcc -g -Wall -Wvla -Werror test_read.c read_ppm.c -o test_read
$ ./test_read
Testing file feep-raw.ppm: 4 4
(0,0,0) (100,0,0) (0,0,0) (255,0,255)
(0,0,0) (0,255,175) (0,0,0) (0,0,0)
(0,0,0) (0,0,0) (0,15,175) (0,0,0)
(255,0,255) (0,0,0) (0,0,0) (255,255,255)

Requirements/Hints:

  • Your function should return NULL if the filename is invalid

  • Your function should return NULL if memory cannot be allocated for the image data

  • Your function should return a pointer to the array you create in read_ppm

  • You can assume that it is safe to read the header line by line (e.g. using fgets).

  • Don’t forget to free your data!

  • Do not modify read_ppm.h. And do not remove the version of the function you do not implement!

  • Make sure your program compiles using the Makefile

  • You can assume the PPM file has a single comment line, starting with #

2.3. Write PPM

Implement a new function, write_ppm, defined in write_ppm.c. Similarly to Assignment 04, you should choose one definition of write_ppm to implement, depending on whether you use either a "flat array" or an "array of arrays" to store your pixels.

In the file, test_write.c, write a short test that reads in feep_raw.ppm and then writes it to a file test.ppm by calling your function. Then, read in test.ppm and print the contents. If it is working correctly, you will see the following pixel values.

$ make test_write
gcc -g -Wall -Wvla -Werror test_write.c write_ppm.c read_ppm.c -o test_write
$ ./test_write
Testing file feep-raw.ppm: 4 4
(0,0,0) (100,0,0) (0,0,0) (255,0,255)
(0,0,0) (0,255,175) (0,0,0) (0,0,0)
(0,0,0) (0,0,0) (0,15,175) (0,0,0)
(255,0,255) (0,0,0) (0,0,0) (255,255,255)

Requirements/Hints:

  • Use fprintf to write the header and fwrite to write the binary Data to your file.

  • Do not modify write_ppm.h. And do not remove the version of the function you do not implement!

  • Make sure your program compiles using the Makefile

  • Don’t forget to write the header comment!

3. Submit your work

Push you work to github to submit your work.

$ cd A05
$ git status
$ git add *.c
$ git status
$ git commit -m "assignment complete"
$ git status
$ git push
$ git status

4. Grading Rubric

Assignment rubrics

Grades are out of 4 points.

  • (2 points) crossword

    • (0.1 points) style and header comment

    • (0.9 points) correct behavior: asks the user for input and creates the new string

    • (1.0 points) no memory errors

  • (1 points) Read PPM

    • (0.1 points) style

    • (0.4 points) correct behavior: reads the PPM file in binary format

    • (0.5 points) no memory errors

  • (1 points) Write PPM

    • (0.1 points) style

    • (0.4 points) correct behavior: write the PPM file in binary format

    • (0.5 points) no memory errors

Code rubrics

For full credit, your C programs must be feature-complete, robust (e.g. run without memory errors or crashing) and have good style.

  • Some credit lost for missing features or bugs, depending on severity of error

  • -5% for style errors. See the class coding style here.

  • -50% for memory errors

  • -100% for failure to checkin work to Github

  • -100% for failure to compile on linux using make