---
description: 600 - 800 points
---

# A7: Bitmap

{% hint style="info" %}
**CMake targets:** `a7-encode` `a7-decode`&#x20;

```bash
cmake --build .build --target a7-encode a7-decode
```
{% endhint %}

On April 3, 1990, Dilbert was sent to the tiny country of Elbonia on a [secret mission](https://dilbert-viewer.herokuapp.com/1990-04-03): to infiltrate the [formerly communist, newly capitalist country](https://dilbert-viewer.herokuapp.com/1990-04-02) and find targets who could become Western engineers. Secretly, Dilbert was also charged with becoming a liaison to the resistance movement from within Elbonia’s totalitarian neighbor, North Elbonia. It has been over three decades, and the mission is still on... with a twist. The governments of Elbonia and North Elbonia have joined forces and together tightened their grip on information. Instagram, X, and TikTok have all been banned. Searches on duckduckgo.com are often filtered out or redirected to NorthElbonia-SearchAndTortureDept.com.

You are the new tech assistant of Dilbert. Your mission is to build a tool for transmitting hidden and encrypted messages. All communications, including images, are controlled. However, images of national art are allowed to be sent.

Elbonian art is based on white noise rectangles, that is rectangles filled with a seemingly random collection of white and black pixels. Unsurprisingly, even the white noise is controlled in Elbonia, the Elbonian Ministry of Mud approves a single pattern every year as that year’s white noise. This year, the pattern seems to be:

```
WWWWWWWWBBBBBBBBWWWWBBBBWWBBBWWR
```

where `W` stands for a white pixel, `B` stands for a black pixel, and `R` stand for a red pixel (used as a delimiter at the end. The white noise images are then made up by repeating this pattern for a total of 32 times vertically. An example of the final image can be seen below.

<details>

<summary>Official 2025 Elbonian White Noise Pattern (upscaled)</summary>

<img src="https://446709468-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkIfjAP0St3jlymiCJIij%2Fuploads%2Fgit-blob-e358666cd05cc76a1e72e147c0ec69777c280d64%2Fa7-image-original%20(upscaled).jpg?alt=media" alt="" data-size="original">

</details>

***

## Assignment (600 points)

Using Assembly, build a tool to encrypt messages into (as well as decrypt messages from) this year's Elbonian white noise pattern in the form of Bitmap image files.

To ensure the absolute highest level of security, message processing and encryption encompasses multiple steps:

1. Compress the message using Run-Length Encoding (RLE).
2. Encrypt the compressed message using XOR encryption.
3. Create a BMP file with an image of this year's white noise pattern and hide the message in it.

Each of the steps is further described below.

### Subroutines

Implement (in the `a7-bmp-encode.S` and `a7-bmp-decode.S` files respectively) subroutines with the following signatures:

```c
void bmp_encode(const char *msg, const char *key, FILE* file);
void bmp_decode(char *buf, const char *key, FILE* file);
```

For encoding, the `msg` argument gives the null-terminated UTF-8 message that should be encoded. For decoding, `buf` points to a  buffer with enough space allocated to fit the original, decoded message. `key` is the key to use for XOR encryption and decryption, and `file` is a file pointer to a file stream opened for writing (`bmp_encode`) or reading (`bmp_decode`).

You may safely assume that Dilbert will never send a message longer than 768 characters.

### Main Programs

For encoding, the `main` program should take the path for the output file as its first command line argument and the message to be encoded as the second. So to encode "Hello World" into a file named image.bmp, the invocation would look as follows:

```bash
./a7-bmp-encode image.bmp "Secret Key" "Hello World"
```

The `main` program for decoding is similar, however, without the message argument, so:

```bash
/a7-bmp-decode image.bmp "Secret Key"
# Hello World
```

Internally, these programs should open the given file (for writing or reading respectively) and then call your `bmp_encode` or `bmp_decode` subroutine for further processing.

### Shared Functions

If you have functions that you want to use for both encoding and decoding, you can place them in the `a7-bmp-shared.S` file, which will be compiled with both programs. Make sure to add the required `.global` declarations as indicated by the example in the file.

***

## Individual Steps

{% hint style="warning" %}
If you haven't done so before, this assignment is **really** the point at which is advisable to structure your code into multiple functions offering abstractions for the different parts needed. For example, you ~~could~~ **should** create subroutines for RLE-encoding and decoding respectively.

It is also very important to work closely with the debugger and ASan. This assignment is extremely prone to memory errors, leading to tests failing in the CodeGrade environment.&#x20;
{% endhint %}

### Run-Length Encoding

Run-Length Encoding (RLE) is one of the simplest data encoding techniques. RLE is based on the notion of runs, which are sequences of specified lengths of the same item. For this assignment, you will use RLE-8, which encodes, in turn, the size of the sequence and each item on 8 bits each. For example, the RLE-8-encoded sequence of two bytes "5X" means that the sequence length is 5 and the item is 'X', for the fully decrypted text "XXXXX".

Runs longer than 9 characters (e.g., "AAAAAAAAAAAA") are split into multiple parts (`0x09 A 0x03 A`) in the encoding.

{% hint style="info" %}
It may help to develop the RLE-encoding and decoding subroutines in close coordination. You may test whether they can successfully compress and decompress a message before continuing with the next step.
{% endhint %}

{% hint style="success" %}
You can safely assume that the message transmitted is a regular **UTF-8 message**, containing only [ASCII characters](https://en.wikipedia.org/wiki/UTF-8#Byte_map). Therefore, you may reserve bytes `0x01` to `0x09` specifically for Run-Length Encoding.

**Extra hint**: Will you ever need to use the byte `0x01` in RLE?
{% endhint %}

### XOR Encryption

One of the common logical operations is the eXclusive OR (XOR, $$\oplus$$). Two properties of XOR are of interest:

$$
x \oplus0=x \newline x \oplus x = 0
$$

From the above equations, it is trivial to observe that:

$$
\begin{aligned}\left(x \oplus y\right) \oplus y &= x \oplus\left(y\oplus y\right) \\ &=x \oplus 0 \\ &= x \end{aligned}
$$

This means that we can use XOR to first encrypt ($$x \oplus y$$) and then decrypt ($$\left (x \oplus y \right)\oplus y$$) a one-bit message $$x$$ with the key $$y$$. It turns out that these two one-bit operations can be extended to $$n$$-bit operations, that is, for an $$n$$-bit message $$M$$ and an $$n$$-bit key K:

$$
\left(M\oplus K\right) \oplus K = M
$$

If the size of the message is $$n$$ bits and the size of the key is $$k < n$$ bits, the key can be repeated until the whole message is encrypted.

### BMP File Format

Storing data as images requires complex data formats. One of the simplest is the bitmap (BMP) format, which you will use for this assignment. BMP files encode raster images, that is, images whose unit of information is a pixel; raster images can be directly displayed on computer screens, as their pixel information can be mapped one-to-one to the pixels displayed on the screen.

The BMP file format consists of a header, followed by a meta-description of the encoding used for pixel data, followed sometimes by more details about the colors used in the image (look-up table). The BMP file format is versatile, that is, it can accommodate a large variety of color encodings, image sizes, etc. It is beyond the purpose of this Manual to provide a full description of the BMP format, which is provided [elsewhere](http://en.wikipedia.org/wiki/BMP_file_format). (_Note: Although Wikipedia is not a universally trustworthy source of information, many of its articles on technical aspects, such as the “BMP file format” have been checked by tens to hundreds of domain experts_.)

Luckily for you, of the many flavors of encodings, Elbonian authorities only accept one type. Thus, you must use the following BMP format for this assignment:

1. **File Header,** encoded as signature (two bytes, `BM` in ASCII); file size (integer, four bytes); reserved field (four bytes, `0x0 0x0 0x0 0x0`); offset of pixel data inside the image (integer, four bytes).\
   The file header size is 14 (two bytes for signature and four bytes each for file size, reserved field, and offset of pixel data). The file size is the sum of 14 (the file header size), 40 (the size of the bitmap header), and the size of the pixel data.
2. **Bitmap Header**, encoded as: header size (integer, four bytes, must have a value of 40); width of image in pixels (integer, four bytes, set to 32–see paragraph on white noise); height of image in pixels (integer, four bytes, set to 32–see paragraph on white noise); reserved field (two bytes, integer, must be 1); the number of bits per pixel (two bytes, integer, set here to 24); the compression method (four bytes, integer, set here to 0–no compression); size of pixel data (four bytes, integer); horizontal resolution of the image, in pixels per meter (four bytes, integer, set to 2,835); vertical resolution of the image, in pixels per meter (four bytes, integer, set to 2,835); color palette information (four bytes, integer, set to 0); number of important colors (four bytes, integer, set to 0).
3. **Pixel Data**, encoded as B G R triplets for each pixel, where B, G, and R are intensities of the blue, green, and red channels, respectively, with values stored as one-byte unsigned integers (0–255). It is important that the number of bytes per row must be a multiple of 4; use 0 to 3 bytes of padding, that is, having a value of zero (0) to achieve this for each row of pixels. The total size of the pixel data is $$N_{rows} \times S_{row} \times 3$$, where $$N_{rows}$$ is the number of rows in the image (32, see paragraph on white noise); $$S_{row}$$ is the size of the row, equal to the smallest multiple of 4 that is larger than the number of pixels per row (here, 32–see paragraph on white noise); and the constant $$3$$ is the number of bytes per pixel (24 bits per pixel, as specified in the field “number of bits per pixel”, see the Bitmap header description).

***

## Requirements

To pass the basic assignment, your programs should follow the following requirements:

1. Implement all three [individual steps](#individual-steps).
2. The UTF-8 message must be hidden inside the image.\
   You cannot store the message at the end of the image and call it a day. The totalitarian government is aware of these empty tricks and will catch you! Therefore, your file size must be exactly **3126 bytes**, only including the data mentioned in the [BMP file format](#bmp-file-format) section.
3. The image must not show significant modifications.\
   This will be automatically tested by the CodeGrade environment. The threshold for the basic assignment is an absolute difference from the original image of at most `0x14` in any of the red, green, or blue bytes of any pixel $$(x, y).$$\
   $$\forall (x, y), \quad |R'(x, y) - R(x, y)| \leq 20, \quad |G'(x, y) - G(x, y)| \leq 20, \quad |B'(x, y) - B(x, y)| \leq 20$$
4. The decode program must exit gracefully, without any address sanitization errors **when entering a wrong password** (you should simply display the message resulting in xor-decrypting with the wrong key, _hopefully different from the original message_).

{% hint style="warning" %}
Note that the appearance of the image will **also be judged by the TA** handling your submission. We may reject submissions that show severe artifacts or differences from the original image, despite passing the tests.
{% endhint %}

***

## Recommended Approach

There are (as always, but especially for this assignment) many different approaches. Below are some example steps that might help but can also safely be ignored.

1. Start by conceptually developing an algorithm to hide the message inside the B G R bytes of the available pixels. Try pushing your algorithm to the limits (on paper) and calculate the maximum absolute difference from the original image in any of the B G R bytes of any pixel.&#x20;
2. Implement the individual parts of message processing. Test the individual parts of compression/decompression or encryption/decryption.
3. Try to create an empty/black BMP file and see if you can open the file with a regular image viewer. If viewing the file fails, there is likely something wrong in the header or body of your image file. It may help to use a hex viewer to look at the file contents to find the issue.
4. Combine all the parts! (... and see if you maybe should continue your studies at the Secret Service of your choice.)

***

## Bonus (200 points)

Dilbert is [extra paranoid](https://www.openbsd.org/security.html) and wants to make sure his message will never be detected. Your task is to ensure that the image does not differ from the original at all, with a _dynamic pixel threshold_ based on the message length. Dilbert wants short messages to be even harder to detect than longer messages.

In short, there should be no visible artifacts in the image for any message length. On top of that, messages shorter than 382 characters should have an absolute difference from the original image of at most `0x01` in any of the red, green, or blue bytes of any pixel. This threshold is increased to `0x03` for messages longer than 382 characters.

{% hint style="warning" %}
The quality of your image will be automatically assessed by the CodeGrade environment. Even if your image _looks the same_ as the original, we expect you to develop an algorithm that satisfies the _dynamic pixel threshold_ requiremen&#x74;_._

We also expect the images to look **the same** as the original to the human eye. This will also be judged by the TA handling your submission, reserving their right to reject a bonus submission if the images display any form of artifacts.
{% endhint %}
