The 1000-year clock has chimed again for the renewal of ancient runes. Thousands of runestones have faded and must be regenerated to prevent the forest from darkening forever. The task falls to Gregor, the last wizard who knows the secret of the stones. Using a computer and a C compiler, we can help him: the runes mimic fractal structures that can be reproduced using linguistic algorithms. I will implement an interactive program that reads commands, performs corresponding operations on an image, and displays the result. Images will be loaded and saved using the binary PPM color image format.
Objectives:
- Work with arrays, dynamic allocation, and simple data structures, including storing state for UNDO and REDO commands.
- Practice deep copying program state for undo/redo operations.
- Work with binary files (PPM images read/written with fread/fwrite).
- Work with text files (.lsys and .bdf formats).
- Binary data representation for the engraving/BITCHECK task.
The program will start without command-line parameters and will accept commands from standard input, one per line. For each command, the program will perform the requested operation and print a success or error message to the screen. Commands are read and executed until the EXIT command is encountered, which stops execution, frees all resources, and closes files. Any unrecognized command will result in the message "Invalid command" and will have no other effects.
Undo and Redo Logic: Commands that successfully modify the program's state are considered undoable.
- UNDO: Cancels the effect of the last un-canceled undoable command. If non-undoable commands (like SAVE) are executed between an undoable command and an UNDO, they are ignored by the UNDO process and remain executed. If no undoable command has been executed, UNDO fails with the message "Nothing to undo".
- REDO: Executes the last canceled command. If there is no last canceled command or if new undoable commands were executed after the last cancellation, REDO fails with the message "Nothing to redo".
A .ppm file in this assignment is a binary file in the PPM P6 format. The header is ASCII text, and the pixel matrix is stored as binary bytes.
- Line 1: Magic bytes identifying the format: P6.
- Line 2: The 2 dimensions of the image (width and height) in ASCII format.
- Line 3: The maximum value of a color channel (in this case, 255).
- Binary Data: Starting from the next line, the rows of the pixel matrix are represented sequentially from top to bottom. Each row contains pixels encoded from left to right. The R, G, and B channels of each pixel are represented in base 2 with one byte each.
- Byte Order: The bytes are ordered R, then G, then B.
We define a Lindenmayer system (L-system) as a triplet (V, axiom, P).
- V (the alphabet) is a finite set of printable ASCII characters.
- The axiom is the starting string of symbols from V.
- P is a set of production rules where a symbol is replaced by a successor string. If a symbol has no rule, the implicit rule is that it remains unchanged. The string can be derived repeatedly.
Commands:
LSYSTEM <file>: Loads an L-system from the specified file into memory, replacing any existing one. Success: "Loaded<file>(L-system with<nrules>rules)". Undoable on success. Failure: "Failed to load<file>".DERIVE <n>: Produces and prints to standard output the n-th derivation of the current L-system. Failure: "No L-system loaded" if none exists in memory.
The .lsys File Format:
- Line 1: The system axiom (string without spaces).
- Line 2: An integer representing the number of rules.
- Next lines: The rules, formatted as
<symbol> <successor>separated by a space.
We associate derived symbols with instructions for a turtle that draws lines on images. A graphics system consists of an image, turtle state, and a stack vector S.
- The image is a matrix of pixels where (0,0) is the bottom-left corner.
- The turtle exists in a Cartesian system with a position (x, y) and an orientation angle relative to the positive horizontal axis.
- Movement uses a movement step (distance) and an angular step (degrees).
- The vector S saves and restores state using push and pop operations.
Turtle Instructions:
F: Turtle moves forward, drawing a 1-pixel thick line on the image.+: Turtle orientation increases by the angular step.-: Turtle orientation decreases by the angular step.[: Current position and orientation are pushed to the end of vector S.]: Turtle returns to the position and orientation popped from vector S (does not draw a line).- Any other symbol: System remains unchanged.
Bresenham's Line Algorithm: Because a line is continuous, it must be approximated discretely using Bresenham's algorithm. The algorithm traverses from one end to the other, deciding at each step whether to move straight or diagonally based on an accumulated error margin. Any correct implementation of Bresenham is accepted.
Commands:
LOAD <file>: Loads a PPM image into memory, replacing the current one. Success: "Loaded<file>(PPM image<width>x<height>)". Undoable. Failure: "Failed to load<file>".SAVE <file>: Saves the current image to a PPM file. Success: "Saved<file>". Failure: "No image loaded".TURTLE <x> <y> <d> <angle> <delta> <n> <R> <G> <B>: Sets the turtle at (x, y) with starting angle, movement step d, and angular step delta. It interprets the n-th derivation of the active L-system to draw lines of color (R, G, B). Failure: "No image loaded" or "No L-system loaded". Success: "Drawing done". Undoable on success.
To write text on the image, we load a bitmap font (BDF format) where each typographic glyph is defined as a matrix of 0s and 1s.
Commands:
FONT <file>: Loads a BDF bitmap font, setting it as current and replacing the old one. Success: "Loaded<file>(bitmap font<name>)". Undoable. Failure: "Failed to load<file>".TYPE "<string>" <start_x> <start_y> <R> <G> <B>: Draws the string on the current image starting at (start_x, start_y) using the active font and specified RGB color. Success: "Text written". Undoable. Failure: "No image loaded" or "No font loaded".
BDF Format Details:
FONT <font name>: Defines the full name of the font.STARTCHAR,ENCODING <ascii code>: Identifies the specific character.DWIDTH <dwx> <dwy>: The number of pixels the cursor moves after writing this character.BBX <BBw> <BBh> <BBxoff> <BByoff>: The bounding box dimensions and the offset for the bottom-left corner relative to the cursor position.BITMAP: Followed by BBh lines of hexadecimal data. Each line represents a row of pixels, padded with zeros to the right until it reaches a multiple of 8 bits.
The generated image is sent to an engraving machine, but an adapter might misread signals due to clock interference. If we look at the contiguous bit stream of the RGB bytes across the image rows, the adapter might misread the bit sequence 0010 as 0000, and 1101 as 1111.
Command:
BITCHECK: Scans the image's bit sequence and prints a warning for every 0010 and 1101 sequence found. Failure: "No image loaded". Success: "Warning: pixel at (<x>,<y>) may be read as (<R'>,<G'>,<B'>)". It must display the coordinates of the pixel containing the flipped bit, and the resulting decimal RGB value if it were misread.