Assignment 6: Secret messages

Due Wednesday, March 1, before midnight

The goals for this assignment are:

Understand binary representations of data types
Directly manipulate basic types at the bit level
Work with bitwise operators: |, &, ~, ^

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 A06.

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

Tiny Bitmaps

A 1bpp, or 1-bit-per-pixel, sprite stores a grid of black and white pixels using a single bit. 0 denotes white and 1 denotes black.

In the program, bitmap.c, implement a program that reads in a single 64-bit unsigned integer (e.g. unsigned long) and outputs it as an 8x8 1bpp sprite.

$ ./bitmap < bitmap1.txt
Image (unsigned long): ff818181818181ff
@ @ @ @ @ @ @ @
@             @
@             @
@             @
@             @
@             @
@             @
@ @ @ @ @ @ @ @
----

Requirements/Hints:

Your program should must use a bitmask! For example, to generate a 64-bit mask that obtains the left-most bit, do 0x1ul << 63. The ul indicates an unsigned long value. 0x1 is the number one in hexadecimal.
The bitmap files store the values as hexadecimal values. To read them in, do unsigned long img; scanf(" %lx", &img);. Use %lx for printf also. You are given basecode that reads in the long integer from stdin.

Steganography

Steganography is the practice of hiding messages in plain sight. In this question, we will hide text messages using the least significant bits of an image.

Background

Credit: Chris Trailie (Original)

To understand how we will hide messages in the least significant bits of an image, let’s look at the following write-up by Chris Trailie, starting with the two pictures below.

Ordinary image	Hidden message

The picture on the right contains 12 paragraphs of text on the Ursinus 150 strategic plan. Can you see the difference? No? Well great, that's the point!

So how do we do this? The idea is beautifully simple, and is best understood with an example. Consider the following 3-pixel image

[254, 119, 50]

[2, 141, 254]

[91, 159, 64]

We're going to extract a binary signal by looking at the least significant bit (the 1's place in binary) of each color channel in each pixel from left to right from red, to green, to blue, and put them together into one binary string. In other words, for a particular pixel and a particular color channel, we'll extract a 0 if it's an even number and a 1 if it's an odd number. Let's look at the first 8 bits in the above image. We have

254	0
119	1
50	0
2	0
141	1
254	0
91	1
159	1

All together, this is the binary string 01001011, which is the character 'K' in ASCII. What if we wanted to change it to some other character though? Perhaps the character 'z', which is 0x7A hex, or 01111010 in binary. Then we can just tweak the 1's place of the pixel values as follows, where I've bolded the ones that have changed:

254	0
119	1
51	1
3	1
141	1
254	0
91	1
158	0

Here's what these updated values look like

[254, 119, 51]

[3, 141, 254]

[91, 158, 64]

If you were just looking at it and comparing it to what we started with, you would never notice the difference! So we have freedom to tweak the least significant bit of every color channel of every pixel at will to encode text, and this is exactly what you will be doing in this assignment!. In a 500x500 image, for example, this means we can store 250,000 bits. Since each ASCII character is 8 bits, this is 31,250 characters total, or roughly about 6000 words.

1. Decode

In the file, decode.c, write a program that reads in a PPM file (raw, or binary, format) and then outputs any message that might be stored in the least significant bits of each color. Your program should read bits from each of the red, green, and blue colors — top to bottom, left to right. You should keep decoding until you reach the empty character \0.

For example, consider the example file tiny_encoded.ppm. Decoding should give you the bits 001100010011011100110100001000010000101000000000.

If we group them up into ASCII char variables, we see this is the character string 174!\n.

00110001	`'1'`
00110111	`'7'`
00110100	`'4'`
00100001	`'!'`
00001010	`'\n'`
00000000	`'\0'`

Your program should perform as follows.

$ ./decode tiny_encoded.ppm
Reading tiny_encoded.ppm with width 4 and height 4
Max number of characters in the image: 6
174!

Requirements/Hints:

You should read the PPM filename as a command line argument
You should report the usage if no file is given to the program
You should report an error if the file cannot be read
Re-use your implementation of read_ppm and write_ppm from Assignment 05.
Output the size of the image along with the maximum number of characters it can store
For debugging, try printing out values in hex format, e.g. printf("%02X", c);
This question is a little easier if you use a 1D array because you can cast the struct ppm_pixel* array to an unsigned char* array.

2. Encode

In the file, encode.c, write a program that reads in a PPM file (raw, or binary, format) and asks the user for a message to embed within it.

$ make encode
gcc -g -Wall -Wvla -Werror encode.c read_ppm.c -o encode
$ ./encode feep-raw.ppm
Reading feep-raw.ppm with width 4 and height 4
Max number of characters in the image: 5
Enter a phrase: lol
Writing file feep-raw-encoded.ppm

Requirements/Hints:

You should read the PPM filename as a command line argument
You should report the usage if no file is given to the program
You should report an error if the file cannot be read
You should output a new file based on the input name. For example, if the input is feep-raw.ppm, the new file with the encoded message should be feep-raw-encoded.ppm.
Re-use your implementation of read_ppm from Assignment 05.
Output the size of the image along with the maximum number of characters it can store
For debugging, try printing out values in hex format, e.g. printf("%02X", c);

3. Submit your work

Push you work to github to submit your work.

$ cd A01
$ 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.

(1 points) bitmap
- (0.1 points) style and header comment
- (0.4 points) uses bitwise operators to display the image in ASCII
- (0.5 points) no memory errors
(1 points) Decode
- (0.1 points) style and header comment
- (0.65 points) correct behavior
- (0.75 points) no memory errors
(1.5 points) Encode
- (0.1 points) style and header comment
- (0.65 points) correct behavior
- (0.75 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