代写CSC 230程序、代做C/C++，CSS程序设计

日期：2021-04-08 11:37

CSC 230 Project 5

Lossy Image Compression

Images have been a common subject for compression. There are a couple of reasons for this. Without compression, image data

can require a lot of storage space, and images are often tolerant of a small amount of loss. It's generally OK if the compressed

image doesn't capture the original image exactly. If it can make the compressed representation smaller, most applications are

able to accept small changes in the intensity values stored in some pixels of the image.

This is what you'll be working on in this assignment. You'll be writing a pair of programs that compress and decompress grayscale

images. We'll be using a technique that's kind of like how the JPEG image format works. We'll be breaking the image into a lot of

little square blocks, applying a transformation called the Discrete Cosine Transform (DCT) to each block, then encoding the result

using different numbers of bits for various values. We'll call our compressed format j10, since it's like a simplified JPEG format,

but it uses 10 x 10 image blocks rather than the 8 x 8 blocks normally used by JPEG.

Our image compression program will be called encode. The following shows how we can run it. Here, the program will read an

input image named "image-06.pgm" and write out a compressed image named "output.j10".

$ ./encode image-06.pgm output.j10

We won't be able to directly display images in the j10 format. It's a format we just made up for this assignment, so no standard

image viewing program will support it. To view a compressed image, we'll need to first decompress it to PGM. Then, we can view

the resulting PGM image. Our decompression program will be called decode. The following shows how we can run it, taking the

compressed image we just created and decompressing it to produce an image in the standard, pgm format.

$ ./decode output.j10 output.pgm

The figure below shows the results of this compression and decompression. The image on the left is the original, and the one on

the right is the result of compressing and decompressing this image. There are some small differences. That's what you would

normally expect from a lossy compression technique. Overall, the two images look very similar.

Original image (left) and compressed/decompressed image (right)

If we're willing to tolerate some small differences introduced by compression, a lossy technique can save a lot of storage space.

The shell commands below show that we've reduced the storage cost for this image by more than 2/3. The original image

required almost 208 kilobytes, but the compressed representation used only about 63.

$ ls -l image-06.pgm output.j10

-rw-r--r-- 1 dbsturgi staff 212816 Mar 27 10:45 image-06.pgm

-rw-r--r-- 1 dbsturgi staff 64959 Mar 28 10:48 output.j10

As with recent assignments, you'll be developing this project using git for revision control. You should be able to just unpack the

starter into the p5 directory of your cloned repo to get started. See the Getting Started section for instructions.

This Project supports a number of our course objectives. See the Learning Outcomes section for a list.

Rules for Project 5

2021/4/5 CSC230 Project 5 –

https://www.csc2.ncsu.edu/courses/csc230/proj/p5/p5.html 2/17

You get to complete this project individually. If you're unsure what's permitted, you can have a look at the academic integrity

guidelines in the course syllabus.

In the design section, you'll see some instructions for how your implementation is expected to work. Be sure you follow these

rules. It's not enough to just turn in a working program; your program has to follow the design constraints we've asked you to

follow. For this project, we're putting some constraints on the functions you'll need to define, and on one data structure you'll

need to use. Still, you will have lots of opportunities to design parts of the project for yourself.

Requirements

This section says what your programs are supposed to be able to do, and what they should do when something goes wrong.

Encode / Decode Execution

The encode program expects two command-line arguments, the name of an uncompressed input image in PGM format and the

name of a file for storing the compressed image in our j10 format. For example, you should be able to run it as follows:

./encode input.pgm output.j10

If you give the program the wrong number of command-line arguments, it should print the following line to standard error and

then terminate with an exit status of 1.

usage: encode <input.pgm> <output.j10>

If one of the given files can't be opened, the program should print an error message to standard error, then terminate with an exit

status of 1. The error message should be generated using the perror() standard library function, with the filename passed to

perror() as the argument. For example, on a common platform system, you'll get an error message like the following if you try to

open a file that doesn't exist. Since the specific message is determined by perror(), you may get different error messages on

other systems of for different kinds of errors.

input.pgm: No such file or directory

If the input image isn't valid (see the description of the raw PGM format below), the encode program should print the following

line to standard error and then terminate with an exit status of 1. An input image could be invalid if the header didn't have the

expected fields, if the maximum intensity value wasn't 255, or if the file wasn't large enough to contain a byte for each pixel. Our

compression technique also requires image width and height to both be a multiple of 10 (there's an extra credit option described

below that lifts this restriction). If you don't do the extra credit, you should also report this error for images that don't have a

width and height that meet this constraint.

Invalid image file

As you'll see below, our compression technique will only support files with a width and height that are both less than 4096 pixels.

The encode program should also print the above message and terminate with a status of 1 if the input image is too wide or too

tall.

The decode program is similar to encode; it expects two command-line arguments, the name of a compressed input file in our j10

format and the name of an output file for the uncompressed image in PGM format. For example, you should be able to run it as

follows:

./decode input.j10 output.pgm

If you give the program the wrong number of command-line arguments, it should print the following line to standard error and

then terminate with an exit status of 1.

usage: decode <input.j10> <output.pgm>

If one of the given files can't be opened, decode will also use perror() to print an error message to standard error, then terminate

with an exit status of 1. So, it might print an error message like the following if it couldn't create the requested output file:

output.pgm: Permission denied

If the decode program is given an input file that doesn't contain enough bits to represent an encoded image (if the input file

reaches the end-of-file before it should), it should print the following line to standard error and then terminate with an exit status

of 1. Unless you do the extra credit, you should also print this line and terminate if the input describes an image where the width

and height aren't a multiple of 10.

Invalid encoded file

PGM Image Format

For uncompressed images, we'll be using the raw form of the PGM image format. This is similar to the image format we used on

project 2, but it represents pixel data in binary, rather than in text. This makes it much more space-efficient (but, our compressed

format will generally be able to do better). We'll place some additional constraints on our input and output images, to make them

easier to parse and to write out.

The raw PGM image format starts with a 3-line header like the following. This part of the file is in text. It starts with two

characters, P5 on the first line. This two-character code indicates that this is an image file in raw PGM format. The next line gives

the size of the image, as width then height. The example below is showing an image 60 pixels wide and 45 pixels tall. Notice that

the width, height order is backward from how we normally describe two-dimensional data. Everywhere else in our program, we'll

generally order these as height (rows) then width (columns). In this one place, though, we have to respect the order defined in

the PGM image format, so, for PGM images, this line of the header will give width then height.

2021/4/5 CSC230 Project 5 –

https://www.csc2.ncsu.edu/courses/csc230/proj/p5/p5.html 3/17

P5

60 45

255

The third line of the header gives the maximum intensity for pixels. All the images we work with will be at least 1 pixel wide and 1

pixel tall, and they'll all have 255 as their maximum intensity. We'll also assume there's just one space between the width and

height.

The 255 at the end of the header is followed by one whitespace character (a newline for all of our images). Then, the remaining

width x height bytes in the file give the intensity values for the image pixels, one byte per pixel. These are given in row-major

order, so the first byte of pixel data gives the intensity of the pixel in the upper-left corner, then the intensity of the next pixel on

the top row, and so on, up to the last pixel on the top row. Then, immediately afterward are all the pixel intensities for the second

row, then the next row all the way to the last row of the image. Note that all the pixel data is in binary, one byte per pixel. There's

no separation between the intensity values for pixels (e.g., no spaces or newlines separating the data values).

The following shows the contents of a small pgm file using the hexdump program. This lets us see the start of the file as text

(over on the right) and the contents of the pixel data as binary. You can see this is a 10 x 10 image. The hexadecimal 0a near the

end of the first line is the newline after the 255. After this, the ad is the intensity of the pixel in the upper-left corner of the

image. This value, along with the 99 bytes after it give the intensity values of all the image's pixels, in row-major order. The file

ends right after the intensity of the last pixel (31 in hexadecimal).

$ hexdump -C image-02.pgm

00000000 50 35 0a 31 30 20 31 30 0a 32 35 35 0a ad a7 9c |P5.10 10.255....|

00000010 8c 79 65 53 43 37 31 ad a7 9c 8c 79 65 53 43 37 |.yeSC71....yeSC7|

00000020 31 ad a7 9c 8c 79 65 53 43 37 31 ad a7 9c 8c 79 |1....yeSC71....y|

00000030 65 53 43 37 31 ad a7 9c 8c 79 65 53 43 37 31 ad |eSC71....yeSC71.|

00000040 a7 9c 8c 79 65 53 43 37 31 ad a7 9c 8c 79 65 53 |...yeSC71....yeS|

00000050 43 37 31 ad a7 9c 8c 79 65 53 43 37 31 ad a7 9c |C71....yeSC71...|

00000060 8c 79 65 53 43 37 31 ad a7 9c 8c 79 65 53 43 37 |.yeSC71....yeSC7|

00000070 31 |1|

The following figure shows what the image above looks like. Here, the image is enlarged considerably to show individual pixels.

Image defined by the PGM file above.

Image Block Transformation

For the pixel data, our compression technique will work by applying a version of the two-dimensional Discrete Cosine Transform

(DCT) to blocks of the image, then writing out an encoding of each of the resulting blocks. The DCT is a common transformation

used in lossy compression tasks. In fact, if you're familiar with the show, "Silicon Valley", the DCT gets mentioned at least once in

the show. The DCT will let us look at the frequency components in each image block, making it possible to store information about

how the shade is changing within a block, rather than just storing intensity values for individual pixels.

The following figure shows what the DCT does. The left-hand side shows a 10x10 image, with intensity values for each pixel. The

right-hand side shows a DCT of this image, with values rounded to integers after the DCT is calculated. After applying the DCT, we

are left with a grid of values, but many of these values will be zero or close to zero. That will make the transformed image easier

to compress, we can represent it in a way that makes it easy to skip over the zero values.

Example DCT Computation for a small image

2021/4/5 CSC230 Project 5 –

https://www.csc2.ncsu.edu/courses/csc230/proj/p5/p5.html 4/17

We will be applying the DCT separately to 10x10-pixel blocks of the input image. Here, we'll describe how to apply the DCT and

its inverse to an individual block. Compressing an image will require applying this transformation to each 10x10 block and

encoding the result in an output file. Decompressing will require decoding each 10x10 block and applying the inverse DCT to that

block.

For an image block, we'll use X[ i ][ j ] to stand for represent the intensities of the individual pixels. So, X[ 0 ][ 0 ] will stand for

the intensity of a pixel in the upper left corner of the block, X[ 0 ][ 9 ] will be the intensity of a pixel in the upper right, X[ 9 ][ 9 ]

will be a pixel in the lower right corner of the block and X[ 9 ][ 0 ] will be the lower left corner. Even though pixel intensities are

integers in the range 0 .. 255, the transformation will expect these integers to be converted to real values (doubles, with values

between 0 and 255).

From the X values representing pixel intensities in a block, we will compute a 10x10 array of real numbers representing the

transformed block. We will call this array, Y and we will use Y[ m][ n ] to stand for a single element of this array. Each element of

Y will be computed as a weighted sum of all the values of the 10x10 X array. So, applying the DCT will be a little bit expensive.

Each of the 100 elements of Y will require computing a different weighted sum of all 100 values in the X array. There are more

efficient ways to compute the DCT, but we won't worry about that for this assignment.

The following formula shows how to compute the value of any Y[ m ][ n ]. In this definition, B stands for the block size of 10. The

constant, S is a scaling factor that we'll set to S = 0.044997. This value for S should make sure the DCT yields values that can be

encoded with a particular number of bits, and it should help to make sure small differences in how the DCT is computed don't

result in different rounding behavior. The values Sm and Sn are also scaling factors. These will usually have a value of 1 except Sm will have a value of 1 / 2 when m = 0 and Sn will have a value of 1 / 2 when n = 0.

Rule to compute the DCT, generating elements of Y from X

For example, these are the (approximate) weights that would be used to compute the value of Y[ 7 ][ 2 ]. With m = 7 and n = 2,

the formula above would multiply each element of X by the weight shown below and add all of these weighted values up to get Y[

7 ][ 2 ].

0.00389 0.00240 0.00000 -0.00240 -0.00389 -0.00389 -0.00240 -0.00000 0.00240 0.00389

-0.00845 -0.00522 -0.00000 0.00522 0.00845 0.00845 0.00522 0.00000 -0.00522 -0.00845

0.00605 0.00374 0.00000 -0.00374 -0.00605 -0.00605 -0.00374 -0.00000 0.00374 0.00605

0.00134 0.00083 0.00000 -0.00083 -0.00134 -0.00134 -0.00083 -0.00000 0.00083 0.00134

-0.00763 -0.00471 -0.00000 0.00471 0.00763 0.00763 0.00471 0.00000 -0.00471 -0.00763

0.00763 0.00471 0.00000 -0.00471 -0.00763 -0.00763 -0.00471 -0.00000 0.00471 0.00763

-0.00134 -0.00083 -0.00000 0.00083 0.00134 0.00134 0.00083 0.00000 -0.00083 -0.00134

-0.00605 -0.00374 -0.00000 0.00374 0.00605 0.00605 0.00374 0.00000 -0.00374 -0.00605

0.00845 0.00522 0.00000 -0.00522 -0.00845 -0.00845 -0.00522 -0.00000 0.00522 0.00845

-0.00389 -0.00240 -0.00000 0.00240 0.00389 0.00389 0.00240 0.00000 -0.00240 -0.00389

The rule to compute the inverse DCT is similar. Given the DCT of a block, Y, the following will compute the value of any X[ i ][ j ].

Each element of X can be computed as a weighted sum of all the elements of Y. As above, S is the scaling factor of 0.044997

(but, notice that we use its reciprocal here), and B is the block size, 10. The scaling factors Sm and Sn are defined the same as

above. They normally have a value of 1, but Sm has a value of 1 / 2 when m = 0 and Sn has a value of 1 / 2 when n = 0. Notice

that, in this formula, variables m and n are used in the summations, so the values of Sm and Sn will depend on which term you're

adding in.

Rule to compute the inverse DCT, generating elements of X from Y

The following table shows an example. These are the (approximate) weights you would use for computing the value of X[ 9 ][ 0 ].

Each of these weights would be multiplied by an element of Y and the weighted values would be added up to get X[ 9 ][ 0 ].

2.22237 3.10421 2.98908 2.80035 2.54266 2.22237 1.84735 1.42685 0.97121 0.49166

-3.10421 -4.33597 -4.17516 -3.91154 -3.55160 -3.10421 -2.58039 -1.99303 -1.35659 -0.68675

2.98908 4.17516 4.02031 3.76646 3.41988 2.98908 2.48469 1.91911 1.30628 0.66128

-2.80035 -3.91154 -3.76646 -3.52865 -3.20394 -2.80035 -2.32780 -1.79794 -1.22380 -0.61953

2.54266 3.55160 3.41988 3.20394 2.90912 2.54266 2.11360 1.63249 1.11119 0.56252

-2.22237 -3.10421 -2.98908 -2.80035 -2.54266 -2.22237 -1.84735 -1.42685 -0.97121 -0.49166

1.84735 2.58039 2.48469 2.32780 2.11360 1.84735 1.53562 1.18607 0.80732 0.40869

-1.42685 -1.99303 -1.91911 -1.79794 -1.63249 -1.42685 -1.18607 -0.91609 -0.62356 -0.31566

0.97121 1.35659 1.30628 1.22380 1.11119 0.97121 0.80732 0.62356 0.42443 0.21486

-0.49166 -0.68675 -0.66128 -0.61953 -0.56252 -0.49166 -0.40869 -0.31566 -0.21486 -0.10877

2021/4/5 CSC230 Project 5 –

https://www.csc2.ncsu.edu/courses/csc230/proj/p5/p5.html 5/17

Bitwise Input / Output

Our j10 format will write out values to the compressed image file using varying numbers of bits. This will let us save space in the

compressed image. If we have a small value that doesn't need an entire byte, we can store it using just a few bits. Or, if there are

some unused bits in a byte of the output we can use them to store part of a value before starting to use bits in the next byte.

We will always use bits in the output starting from the highest-order bit, then the second-highest-order bit and so on until

reaching the low-order bit of that byte. Then, the next bit we have to store will go in the high-order bit of the next byte. For

example, imagine that we started with an empty output file. If we had to write three bits, 011, to they file, they would go in the

three highest-order bits of the first output byte.

Output after writing three bits

Then, if we had to write out four more bits, say 0101, they would go in the next three bits of the same byte, leaving just the

lowest-order bit unused.

Output after writing seven bits

If we next had to write out three bits, say 111, this would use up the last remaining bit of the first byte and the next two bits

would go in the two high-order bits of the next byte.

Output after writing ten bits

Once all needed bits have been stored, there may still be some left-over bits in the last byte. We can't write just part of a byte to

an output file we'll need to decide what to put in any left-over bits in the last byte before that byte is written out to the file. We'll

always fill any remaining bits with zeros before writing out the last byte of a file.

Encoding Compressed Images

Our j10 image format will start with two 12-bit values giving the height and width of the image (notice, the order is the reverse of

the PGM format). The first 12 bits of the output file will give the height of the image (number of rows) and then 12 more bits for

the width (number of columns). With just 12 bits for each of the these values, this format can support images no larger than

4095 x 4095 pixels.

Image size encoded in the first 12 bits of the j10 format.

After the image size, the j10 file will contain an encoding of each 10x10 block of the image. Blocks will be written out in row- major order, with every block at the top of the image written out left-to-write, then every block below these left-to-right until

reaching the bottom of the image. The figure below shows how a 30x40 image would be handled. It would be encoded as 12

10x10 blocks, with three blocks on each row. Blocks would be encoded to the output one after another in the order shown below

(i.e., in row-major order).

2021/4/5 CSC230 Project 5 –

https://www.csc2.ncsu.edu/courses/csc230/proj/p5/p5.html 6/17

Encoding order for blocks in a 30x40-pixel image.

To encode a 10x10 block, we will first transform it via the DCT. This will yield a 10x10 array of real numbers. We will round each

of these numbers to the nearest integer. This will give us a 10x10 array of integers. The following shows an example of what one

such block might look like. This one represents the 10x10 image-03.pgm given in the starter, it contains just one block. This block

illustrates what the DCT often gives us. In the transformed image block, lots of the values are zero. Most of the non-zero values

are up near the upper-left corner. Our compressed image format will save space by using an (moderately) efficient way to skip

over the zeros in the transformed image block.

DCT of the block in image-03.pgm

In the transformed image block, the value in the upper-left corner represents the overall intensity of the block. We will encode it

first as a 7-bit unsigned value (it should never be negative). In the example above, this value is 50, so we would write it out as

0110010 (that's 50 in binary). Computationally, you won't even need to do any conversion to get the binary representation of this

value. Internally, integers are stored in binary, so we can use the bitwise operators to look at their bitwise representation directly.

Encoding of a 7-bit value for the Y[0][0] value in a block

That takes care of the first value in the transformed image block. For the remaining 99, we'll expect a lot of zero values. We'll

write out 99 bits to indicate which of these values are zero and which are non-zero. For each value in the DCT image block, we'll

write out a 0 bit if that value is zero and a 1 bit if the value is non-zero. Bits for each value will be written out in row-major order,

so we'll write out 9 bits for the 9 remaining values in the first row, then 10 more bits for the 10 bits in the next row, all the way to

the last row of the image block.

The following figure shows how the block shown above would be encoded. It still shows the value of 50 encoded in the first 7 bits.

Then, the next 99 bits represent where the non-zero values are in the remaining elements. The last byte still has 6 unused bits in

it.

2021/4/5 CSC230 Project 5 –

https://www.csc2.ncsu.edu/courses/csc230/proj/p5/p5.html 7/17

Encoding of the Y[0][0] term and a bit for each of the remaining 99 values

Next, we will encode the values for the non-zero elements of the DCT block. These will be done in row-major order, but we will

skip the zero values. These values will may be positive or negative, but they will have smaller magnitudes than the value in the

upper-left corner. We will encode a value using one bit to encode the sign, 0 for positive, 1 for negative. This will be followed by 6

bits giving the magnitude of the value (its absolute value). So, for example, a value of -10 would be encoded as a 1 (since it's

negative), followed by 001010 (the value 10 in binary).

The three non-negative values in the sample DCT block above would be encoded as 1001010 (for the -10 in the top fow), then

0001010 (for the 10 in row 2), then 1001010 (for the -10 in row 2). With these values at the end, the encoding of this entire

block would look like the following figure. There's one bit in the last byte that isn't used. If the image had another block after this

one, that bit would be used as the first bit in encoding the next block. Blocks don't need to start or end at a byte boundary.

Encoding of the entire DCT block shown above

2021/4/5 CSC230 Project 5 –

https://www.csc2.ncsu.edu/courses/csc230/proj/p5/p5.html 8/17

The following figure shows what the test input, image-03.pgm would encode to in the j10 format. It's just a 10x10 image, so it

only contains one block. It starts with two 12-bit numbers for the size of the image, then the encoding for the one block in this

image.

Encoding of the entire image-03.pgm test input

The following shows a larger example. This is the j10 encoding of test input image-04.pgm. To make it fit better on the page, it's

broken into two columns. The image-04.pgm input is 20 pixels wide and 10 pixels tall, so it's encoded as two blocks. It starts with

24 bits for the image size, then the encoding of the first (left-hand) block, then the second (right-hand) one. For this image, there

are two unused bits in the last byte. They should be written out as two low-order zeros.

2021/4/5 CSC230 Project 5 –

https://www.csc2.ncsu.edu/courses/csc230/proj/p5/p5.html 9/17

Encoding of the image-04.pgm test input

Decoding Images

Decoding an image requires reading a compressed image in the j10 format and then writing an image out in raw PGM format. The

first 24 bits give the size the output image should be. After this, each 10x10 block of the image can be decoded from the j10

encoding.

To decode a block, you can fill in the values in a 10x10 block of doubles, Y. The first 7 bits of the block's encoding give the value

in the upper-left corner of Y. Then, the next 99 bits tell where the non-zero values are in the rest of Y. After this, you can read

and store values for each of the non-zero elements of Y in row-major order (be sure to set the rest of the values to zero if

needed).

After filling in the Y array for a block, you can apply the inverse DCT to get a 10x10 array of intensity values, X. Each element of X

can be rounded to the nearest integer to get the pixel intensity. Because we're implementing a lossy compression technique, it's

possible you will get a value that's larger than 255 or less than 0 after rounding. If that happens, just clamp the value to the

0..255 range; if it's larger than 255, set it to 255 instead, and if it's smaller than 0 just set it to zero.

After filling in each 10x10 block of the resulting image, write it out as a PGM file to produce the output.

Extra Credit

To simplify our encode and decode programs, they only need to work with images that are a multiple of 10 in both dimensions.

However, if you'd like up to 5 points of extra credit, you can lift this restriction. If an image isn't a multiple of 10 in size, we can

just pad the image with extra pixels when we're computing the DCT. Then, these extra pixels can be discarded when decoding the

image.

For the extra credit, your encode and decode programs should work for images of any (non-zero) size. If the image isn't the right

size, you will compute the DCT as if it was padded with extra rows and columns of pixels, enough to bring its size up to a multiple

of 10 in both dimensions. Additional rows will just contain copies of the bottom row form the input image. Additional columns will

contain copies of the rightmost column. Any pixels added to the lower-right will contain copies of the pixel in the lower-right

corner of the input image.

2021/4/5 CSC230 Project 5 –

https://www.csc2.ncsu.edu/courses/csc230/proj/p5/p5.html 10/17

Padding the image to get extra pixels needed for the DCT.

The starter includes a few files to help you test the extra credit option, if you choose to implement it. The files image-ec-01.pgm

and image-ec-02.pgm are images that aren't a multiple of 10 in size. The files encoded-ec-01.j10 and encoded-ec-02.j10 are the

compressed output you should get if you compress these images. You can test this part with commands like the following:

./encode image-ec-01.pgm output.j10

echo $?

diff output.j10 encoded-ec-01.j10

There are also a couple of decoded-ec-*.pgm files for testing your decode program support for the extra credit option. You try

these with commands like the following:

./decode encoded-ec-01.j10 output.pgm

echo $?

diff output.pgm decoded-ec-01.pgm

Design

Program Organization

Your solution will use five components. Two of these (encode.c and decode.c) will be top-level components, containing a main

functions for the encode and decode programs. The other three (bits.c/bits.h, image.c/image.h and j10.c/j10.h) will contain

functions and some type definitions to be used by the other components.

The following figure shows the dependency between these components. The top-level programs will use the bits, image and j10

components. The j10 component will use bits and image, but bits and image won't need to use j10 or each other.

2021/4/5 CSC230 Project 5 –

https://www.csc2.ncsu.edu/courses/csc230/proj/p5/p5.html 11/17

Dependency structure among the components

Bits Component

The bits component will support reading and writing files one bit at a time. This is a little tricky, since the C library just provides

mechanisms for reading files one or more bytes at a time.

Your bits component will define two struct types, BitReader and BitWriter. These will contain fields to let you read or write a file

one bit at a time. For reading, the BitReader will contain a buffer with room for (at least) 8 bits. When you need to read the first

bit from a file, it will read a whole byte from an input file. It will return the high-order bit from this byte and save the rest in the

buffer. Then, the next 7 bits can be extracted from the buffer before another byte must be read from the file. Like it says in the in

the Bitwise Input / Output section, bits from each byte of a file will be returned in order from the high-order bit to the lowestorder

bit.

Operation of the BitReader and BitWriter

A similar struct, BitWriter, will be used to help save bits one at a time to a file. Using this struct, you can store bits one at a time

in an internal buffer. Then, once 8 bits have been saved, they can all be written out to the file as a single byte. If all the bits in the

last byte aren't needed, they should be filled with zeros and written to the output file when the BitWriter is closed.

You get to define the BitReader and BitWriter structs yourself. You'll need to store a FILE pointer for the file being read from or

written to. You'll also need other fields to keep up with bits being buffered in the struct.

The bits component will provide the following functions. Of course, you can use other functions if you need them, but be sure to

make any additional functions static if they're only used internally in the component.

BitReader *openBitReader( char const *filename )

This function will open the given file for reading and dynamically allocate a new BitReader struct for that file, initialize it and

return a pointer to it. Client code can use this reader to read bits from the file one at a time.

2021/4/5 CSC230 Project 5 –

https://www.csc2.ncsu.edu/courses/csc230/proj/p5/p5.html 12/17

void closeBitReader( BitReader *reader )

Client code will call this function when it's done using a BitReader. It will free any resources used by the given BitReader,

closing the file it's reading from and freeing any memory the reader was using.

int getBit( BitReader *reader )

Client code will call this function to get the next bit from the file the reader is reading from. If the buffer contains any bits

that haven't been returned yet, it will return the next bit from the buffer. If the buffer is empty, it will read the next byte

from the input file and return the high-order bit from that byte. If there are no more bits to read, this function should return

the constant, EOF, to the caller.

BitWriter *openBitWriter( char const *filename )

This creates a new BitWriter struct, opening a file with the given name, allocating space for the BitWriter and initializing its

fields as needed. It returns a pointer to the new BitWriter struct.

void closeBitWriter( BitWriter *writer )

This function frees all resources for the given BitWriter. If there are some buffered bits, they will be written out to the output

file before it is closed, with zero bits used to fill in any low-order bits that were never used.

void putBit( BitWriter *writer, int val )

This function is for writing a bit to the output file. The val parameter will be 0 for writing a 0 bit, or 1 for writing a 1 bit. Bits

will be stored internally in the BitWriter struct until there are 8 of them, then they can be written to the output file as a single

byte.

Image component

The image component provides a struct for representing the contents of a PGM image. It provides functions for reading and

writing an image from a file. The starter includes a definition for the image struct you will be using. The pixels in the image will be

stored with each row in a dynamically allocated array. We will keep up with all the rows using a dynamically allocated array of

pointers, with one pointer pointing to the start of each row. The pix field in the Image struct will hold a pointer to the start of this

array of pointers.

Image struct for representing the contents of a PGM image file

Your image component will provide the following functions. Of course, you can create other functions if you want. Just be sure to

make them static when you can.

Image *makeImage( int rwos, int cols )

This function creates an image of the given size. It should allocate space for all the image pixels, but the intensity values

don't need to be initialized. Client code can use this function to make an image, then fill it in later.

Image *readImage( char const *filename )

This function will create an image, reading its contents from the given file (as a raw, PGM format image).

void writeImage( Image *image, char const *filename )

This function will write the given image (in raw, PGM format) to the file with the given name.

void freeImage( Image *image )

This function will free any resources (memory) used by the given image. Client code can call this function to free an image

when it's no longer needed.

J10Component

The J10 component will contain support for encoding and decoding images in our j10 format. It will provide the following

functions. The first two would normally be internal to the component (static), but they're used by the DCTTest.c program (see

below), so they're not marked as static.

void DCTBlock( double X[ BLOCK_SIZE ][ BLOCK_SIZE ], double Y[ BLOCK_SIZE ][ BLOCK_SIZE ] )

This function computes the Discrete Cosine Transform, reading pixel intensities from the X array and storing the result of the

2021/4/5 CSC230 Project 5 –

https://www.csc2.ncsu.edu/courses/csc230/proj/p5/p5.html 13/17

DCT in

Y. To use this, you'll need to copy individual blocks of pixel data from the input image into a 10x10 array of doubles.

void IDCTBlock( double Y[ BLOCK_SIZE ][ BLOCK_SIZE ], double X[ BLOCK_SIZE ][ BLOCK_SIZE ] )

This function computes the inverse DCT, reading from the Y array and writing pixel intensity values to X.

void encodeImage( Image *image, BitWriter *writer )

This function encodes the given image in the j10 format. It writes bits using the given BitWriter struct.

Image *decodeImage( BitReader *reader )

This function creates a new image and returns a pointer to it,decoding the j10 format to fill in the image pixels. It uses the

given BitReader to extract individual bits from the encoded image.

Encode / Decode Component

These two programs will implement the encode and decode programs, using functions provided by the other three programs.

They will contain the main functions for each program and any other functions you need to simplify your implementation.

Build Automation

You get to implement your own Makefile for this project (called Makefile with a capital 'M', no filename extension). Its default

target should build both your encode and decode programs, compiling each source file to an object file and then linking the

objects together into an executable.

You should already know how to get a Makefile to build multiple programs by default. You'll do this by having a rule like the

following. Put this rule before any other rules in your Makefile and it will be your default target. The make program will try to build

the all target if you don't specify any other target. As prerequisites, all says to just build the two programs, encode and decode.

all: encode decode

As usual, your Makefile should correctly describe the project's dependencies, so targets can be rebuilt selectively, based on what

parts of the project have changed. It should compile source files with our usual command-line options, including -g for help with

debugging. It should also have a clean rule, to let the user all the executables and object files so they can all be rebuilt from

source (say, if you move all your files to a different operating system).

Since you'll be using functions like cos() and sqrt(), you will need to make sure you link with the math library. Also, you'll be using

the constant, M_PI, as a value for pi. From exercise 13, you saw that you need the compile-time flag, -D_GNU_SOURCE to enable

this constant.

Testing

The starter includes a test script, along with test input files and expected outputs. When we grade your program, we'll test it with

this script, along with a few other test inputs we're not giving you. To run the automated test script, you should be able to enter

the following:

$ chmod +x test.sh # probably just need to do this once

$ ./test.sh

This will automatically build your program and see how it does against all the tests.

As you develop and debug your programs, you'll want to be able to run them yourself, to see what they're doing and maybe try

them out inside the debugger. As you run the test script, you'll see it reports on how it's running your program for each test. You

can copy this command to run your program directly to get a better idea of how it's behaving.

The starter also includes a couple of test driver programs, to help you make sure your bits component and your DCT computation

are working correctly. The test driver for the bits component is called bitsTest.c. You can compile it as follows, then run the

bitsTest executable.

gcc -Wall -std=c99 bitsTest.c bits.c -o bitsTest

The bitsTest program will run several tests for writing out and reading in bits using your code, reporting any test that fails. Feel

free to read over the code in this test driver. It's not too complicated, it may help clarify how the bits component is supposed to

work, and it will help you diagnose problems if any of the tests fail.

The DCTTest.c program will run a test of your DCT and inverse DCT transformation on a 10 x 10 array. It will help you make sure

your implementation of these transformations is working the way it's supposed to. You should be able to build this test program

using the following command:

gcc -D_GNU_SOURCE -Wall -std=c99 DCTTest.c j10.c image.c bits.c -o DCTTest -lm

Then, when you run it, DCTTest will call your DCTBlock() and IDCTBlock() functions, reporting if it sees any errors in the results

from either function.

Binary File Report

To help debug, we're providing source code for a simple program that prints out the contents of a file in binary. This may help you

to see if the bit sequences you're trying to write to a file are really making it there. It's called dumpbits.c. You can compile it like

any C program, then redirect standard input from a file to get it to print out the contents of any file in binary. For example, if you

run it as follows, it will show the contents of the encoded representation for test case 1:

2021/4/5 CSC230 Project 5 –

https://www.csc2.ncsu.edu/courses/csc230/proj/p5/p5.html 14/17

$ ./dumpbits < encoded-02.j10

0000 00000000

0001 10100000

0002 00001010

0003 01100101

0004 00000000

0005 00000000

0006 00000000

0007 00000000

0008 00000000

0009 00000000

000a 00000000

000b 00000000

000c 00000000

000d 00000000

000e 00000000

000f 00000000

0010 00001010

0011 00000000

In the right-hand column, this program reports the 8 bits in each byte in the input file. The left-hand column gives the index of

each byte, in hexadecimal.

Memory Error and Leaks

When it terminates successfully, your programs are expected to free all of the dynamically allocated memory they have allocated

and close any files they have opened. When your programs have to exit unsuccessfully, they aren't expected to free all memory or

close all their files. That's because, on an error, your program may have to exit immediately, from within a few function calls.

From there, it might not be possible to access all the memory and files stored in other parts of the program.

Valgrind can help you find memory errors or leaked files. To get valgrind to check for memory errors in one of your programs, you

can run your program like this:

$ valgrind --tool=memcheck --leak-check=full ./encode image-01.pgm output.j10

-lots of valgrind output deletedTo

get it to look for file leaks instead, you can run it like the following. At the end, you'll get a report that file descriptors 0, 1 and

2 are still open. That's normal; those are standard input, standard output and standard error. If you see others, that's probably a

file leak.

$ valgrind --track-fds=yes ./encode image-01.pgm output.j10

-lots of valgrind output deletedRemember,

valgrind will be able to give you a more useful report if you compile with the -g flag, so don't forget it.

Test Inputs

Test cases for the programs use a small collection of test files. Most of these are valid images, but a few of them are invalid so we

can use them to test error handling.

image-01.pgm : This is a small, 10 x 10 image where all the pixels are black.

image-02.pgm : This is a 10 x 10 image containing a smooth gradient. After applying the DCT to the one block in this image,

you should get the following values:

image-03.pgm : This is a 10 x 10 image containing shades that change smoothly across the image. After applying the DCT to

the one block in this image, you should get the following values:

2021/4/5 CSC230 Project 5 –

https://www.csc2.ncsu.edu/courses/csc230/proj/p5/p5.html 15/17

image-04.pgm : This is a 20 x 10 image containing shades that change smoothly across each of the two blocks in the image.

image-05.pgm : This is a 30 x 40 image of a little face icon.

image-06.pgm : This is a 380 x 560 grayscale image of the Mona Lisa, the same image shown at the start of this

assignment.

image-07.pgm : This is a 4100 x 10 image. It's too wide for our compression technique.

image-08.pgm : This is an invalid image. It has a bad magic number at the start.

image-09.pgm : This is an invalid image. It doesn't contain enough pixel data, so a program trying to read it will reach the

end-of-file before it finishes reading all the pixel data.

encoded-10.j10 : this is an invalid input. It's an image encoded to our j10 format, the file doesn't contain all the data it

should. The decode program will reach the end-of-file before it is able to read all the bits it needs.

Most of the tests come in pairs. We encode a PGM image into the j10 format, then there's a corresponding test that decodes the

image. A few of the higher-numbered tests only apply to the encode or the decode program.

Encode Test 01 : This test encodes the image-01.pgm file.

Encode Test 02 : This test encodes the image-02.pgm file.

Encode Test 03 : This test encodes the image-03.pgm file.

Encode Test 04 : This test encodes the image-04.pgm file.

Encode Test 05 : This test encodes the image-05.pgm file.

Encode Test 06 : This test encodes the image-06.pgm file. Since this image is larger, running the test may take a second or

more.

Encode Test 07 : This is a test for error handling. We attempt to encode the image-07.pgm file.

Encode Test 08 : This is a test for error handling. We attempt to encode the image-08.pgm file.

Encode Test 09 : This is a test for error handling. We attempt to encode the image-09.pgm file.

Decode Test 01 : This test decodes the j10 encoding of image-01.pgm.

Decode Test 02 : This test decodes the j10 encoding of image-02.pgm.

Decode Test 03 : This test decodes the j10 encoding of image-03.pgm.

Decode Test 04 : This test decodes the j10 encoding of image-04.pgm.

Decode Test 05 : This test decodes the j10 encoding of image-05.pgm.

Decode Test 06 : This test decodes the j10 encoding of image-06.pgm. Like the encode test for this image, decoding may

take a second or two.

Decode Test 10 : This is a tests for error handling. We attempt to decode the encoded-10.j10 file.

Decode Test 11 : This is a tests for error handling. We attempt to decode with an input file that doesn't exist.

Decode Test 12 : This is a tests for error handling. We attempt to run the decode program with too many command-line

arguments.

Grading

The grade for your programs will depend mostly on how well they function. We'll also expect them to compile cleanly, to follow the

style guide and to follow the given design. We'll also try your programs under valgrind, to see if finds anything to complain about.

Compiling cleanly on the common platform: 10 points

Working Makefile: 5 points

Behaves correctly on all tests: 80 points

2021/4/5 CSC230 Project 5 –

https://www.csc2.ncsu.edu/courses/csc230/proj/p5/p5.html 16/17

Program follows the style guide: 20 points

Handling images of arbitrary size: up to 5 points of extra credit

Deductions

Up to -60 percent for not following the required design.

Up to -30 percent for failing to submit required files or submitting files with the wrong name.

Up to -30 percent penalty for file leaks, memory leaks or other memory errors.

-20 percent penalty for late submission.

Getting Started

To get started on this project, you'll need to clone your NCSU github repo and unpack the given starter into the p5 directory of

your repo. You'll submit by checking files into your repo and pushing the changes back up to the NCSU github.

Clone your Repository

You should have already cloned your assigned NCSU github repo when you were working on Project 2. If you haven't already done

this, go back to the assignment for Project 2 and follow the instructions for cloning your repo.

Unpack the starter into your cloned repo

You will need to copy and unpack the project 5 starter. We're providing this file as a compressed tar archive, starter5.tgz. You can

get a copy of the starter by using the link in this document, or you can use the following curl command to download it from your

shell prompt.

$ curl -O https://www.csc2.ncsu.edu/courses/csc230/proj/p5/starter5.tgz

Temporarily, put your copy of the starter in the p5 directory of your cloned repo. Then, you should be able to unpack it with the

following command:

$ tar xzvpf starter5.tgz

Once you start working on the project, be sure you don't accidentally commit the starter to your repo. After you've successfully

unpacked it, you may want to delete the starter from your p5 directory, or move it out of your repo.

$ rm starter5.tgz

Instructions for Submission

If you've set up your repository properly, pushing your changes to your assigned CSC230 repository should be all that's required

for submission. When you're done, we're expecting your repo to contain the following files. You can use the web interface on

github.ncsu.edu to confirm that the right versions of all your files made it.

encode.c : Main file for the encode program, created by you.

decode.c : Main file for the decode program, created by you.

j10.h : Header for the j10 component, completed by you.

j10.c : Implementation for the j10 component, created by you.

bits.h : Header for the bits component, created by you.

bits.c : Implementation for the bits component, created by you.

image.h : Header for the image component, completed by you.

image.c : Implementation for the image component, created by you.

Makefile : the project's makefile, created by you.

image-*.pgm : Image input files used for testing.

encoded-*.j10 : Encoded image files used for testing.

decoded-*.pgm : Decoded image files used for testing.

estderr-*.txt : Error message output files used for some of the testing.

test.sh : test script, provided with the starter.

.gitignore : a file provided with the starter, to tell git not to track temporary files for this project.

The starter includes some test programs, like dumpbits.c and bitsTest.c. It's OK to have these in your repo if you want to, but

they're not required.

Pushing your Changes

To submit your project, you'll need to commit your changes to your cloned repo, then push them to the NCSU github. Project 2

has more detailed instructions for doing this, but I've also summarized them here.

As you make changes to your project, you'll need to stage new or modified files in the index:

$ git add .

Then, before you commit, it's a good idea to check to make sure your index has the right files staged:

$ git status

Once you've staged a set of related changes, commit them locally:

$ git commit -am "<meaningful message for future self>"

Of course, you haven't really submitted anything until you push your changes up to the NCSU github:

2021/4/5 CSC230 Project 5 –

https://www.csc2.ncsu.edu/courses/csc230/proj/p5/p5.html 17/17

$ unset SSH_ASKPASS # if needed

$ git push

Checking Jenkins Feedback

Checking jenkins feedback is similar to the previous Project. Visit our Jenkins system at http://go.ncsu.edu/jenkins-csc230 and

you'll see a new build job for Project 5. This job polls your repo periodically for changes and rebuilds and tests your project

automatically whenever it sees a change.

Learning Outcomes

The syllabus lists a number of learning outcomes for this course. This assignment is intended to support several of theses:

Write small to medium C programs having several separately-compiled modules

Explain what happens to a program during preprocessing, lexical analysis, parsing, code generation, code optimization,

linking, and execution, and identify errors that occur during each phase. In particular, they will be able to describe the

differences in this process between C and Java.

Correctly identify error messages and warnings from the preprocessor, compiler, and linker, and avoid them.

Find and eliminate runtime errors using a combination of logic, language understanding, trace printout, and gdb or a similar

command-line debugger.

Interpret and explain data types, conversions between data types, and the possibility of overflow and underflow

Explain, inspect, and implement programs using structures such as enumerated types, unions, and constants and arithmetic,

logical, relational, assignment, and bitwise operators.

Trace and reason about variables and their scope in a single function, across multiple functions, and across multiple modules.

Allocate and deallocate memory in C programs while avoiding memory leaks and dangling pointers. In particular, they will be

able to implement dynamic arrays and singly-linked lists using allocated memory.

Use the C preprocessor to control tracing of programs, compilation for different systems, and write simple macros.

Write, debug, and modify programs using library utilities, including, but not limited to assert, the math library, the string

library, random number generation, variable number of parameters, standard I/O, and file I/O.

Use simple command-line tools to design, document, debug, and maintain their programs.

Use an automatic packaging tool, such as make or ant, to distribute and maintain software that has multiple compilation

units.

Use a version control tools, such as subversion (svn) or git, to track changes and do parallel development of software.

Distinguish key elements of the syntax (what's legal), semantics (what does it do), and pragmatics (how is it used) of a

programming language.