Coursework: Week 9, Sketch

As this assignment is going to involve lots of files, it is suggested that you create a new empty folder to work in. (You should do that anyway, for each new assignment or project.)

Reminder: if you download Makefile directly, it is likely to end up as Makefile.txt and you will need to rename it back.

The right hand column of files is for stage 2.

The file sketch.zip contains all the other files, zipped up. If you want to use that rather than download all the others one by one, copy it into your new empty folder, and then unzip it. (On Windows, in general, it is not recommended to use the native Windows unzip facility, because it often doesn't work properly on non-Windows zip files. Either install 7-zip, or install the unzip command in Cygwin/MSYS2.)

No sketch.c file is provided for you to start from. You have to provide it. That means you have to decide what headers to include, define types and constants, design and write functions that carry out the logic of the problem, design and write tests for those functions, and design and write input/output functions.

On the other hand, you won't need to change anything in any of the other files.

Since the .sketch files are binary, you can't view them in an editor or any of the other normal ways. To see what the bytes of a sketch file look like the best bet is to use the od command (see the aside on Unix commands), e.g.:

od -t x1 lines.sketch
0000000  1e 5e c0 1e 40 5e
0000005

A number on the first column like 0000000 says what position in the binary file the line of output refers to, which is useful for larger files. The rest of the line shows you the bytes in hex.

You might want to write a little throw-away experimental program to read and print out sketch files in any way you find helpful. To print out a byte in hex yourself, use printf("%02x\n",b) for example.

A module display.c is provided which uses the SDL graphics library to provide a few simple functions for drawing. Read display.h to see what is provided and, in your sketch.c file, put #include "display.h" near the top. See the aside on SDL for more information about SDL, though you don't need to understand it for this assignment.

You might want to write a little throw-away experimental program to call the display functions, so you can see what they do.

In the Makefile, there are two ways to compile your sketch.c file. One (typing make sketch) links sketch.c with display.c and the SDL library. The other (typing make test or just make) links it with test.c instead. The test.c module provides the same functions as display.c, but doesn't do any graphics. It just checks that the function calls your program makes are the ones expected.

This gives you two layers of testing. At a low level, you can write tests for your own bit-manipulation functions to check that they do what you intended. You can create suitable tests by looking for examples in this assignment description.

At a higher level, you can test the graphics calls you make to functions in display.h by compiling with test.c. In fact you may want to do that most of the time while you are developing. If you can't get SDL working for some reason, you can compile with test.c all the time, and still get credit for your work.

If you run the program with graphics using ./sketch, memory leaks may show up. This is likely to be SDL's fault, not yours, so you can ignore it.

On the other hand, if you test the program with ./test, any memory leaks that show up are likely to be your fault, and need to be investigated.

Since you are going to be working with many files, and there are a lot of opportunities for damaging them, you might like to start using git (with or without a backup repository in the cloud). See the aside on version control for details.

In stage 1, each byte is a self-contained op, telling your program what to do, rather like a processor instruction.

The first (most significant) two bits form the opcode, short for operation code, which is a small integer, in this case 0 to 3, which specifies what the operation does. The other six bits form the operand, which is like the argument to an operator or function, and provides the op with a number to work with.

Ops can be described in an assembly-language style by writing down a symbol for the opcode followed by the operand. For example, the byte sequence 0x03 0x7D can be written DX 3; DY -3

During the replay of a sketch, there is a current (x,y) position, which is initially (0,0) at the top left corner of the drawing area. (Normal across-and-down graphics coordinates are used. They are a compromise between Cartesian and matrix coordinates.) There is also a notional pen, with "pen up" used to represent moving and "pen down" used to represent drawing. The pen is initially up.

The opcodes in stage 1 are:

• Opcode 0 represents a DX operation, which represents a change to the current x position by a given signed number of pixels, in the range -32..31. However, nothing happens yet. The operand is just remembered.
• Opcode 1 represents a DY operation which represents a change to the current y position by a signed number of pixels (-32..31). This opcode causes a move or draw operation to be carried out. If the pen is down, a line is drawn from the current (x,y) position to a new position (x+dx, y+dy) where dx is the remembered operand from a previous DX op, and dy is the current operand. Whether the pen is up or down, the current position is updated and the remembered dx value is set to zero.
• (Opcode 2 won't be used until stage 2.)
• Opcode 3 represents a PEN operation which toggles the pen from up to down or down to up. The operand is ignored, though it is always zero for compatibility with stage 2.

A complex monochrome sketch with no timings is very compact, consisting mostly of pairs of DX and DY bytes.

Why is drawing not included in the DX op? Because then you would only be able to draw horizontal and vertical lines. Lines can be drawn in any direction.

Examples of operation bytes are:

• byte 0x03 (which is 000000112) means DX 3, a movement of 3 pixels to the right
• byte 0x7d (which is 011111012) means DY -3, a movement of 3 pixels up
• byte 0xc0 (which is 110000002) means PEN, switch drawing on or off

The file lines.sketch contains 6 bytes:

1e 5e c0 1e 40 5e

which mean

DX 30; DY 30; PEN; DX 30; DY 0; DY 30

Check that you understand that the sketch ops mean "move to (30,30) then draw a line to (60,30), then draw a line to (60,60)". In particular, DY 0 causes the first draw, and the DX value is implicitly zero in the final DY 30.

Only the first set of sketch files, from lines.sketch to cross.sketch, are relevant to stage 1.

If you stuff everything into one big function, it will be almost impossible to reach the end of the assignment (except by extreme luck or heroism). But if you keep your functions tiny, you may find the development surprisingly smooth and rewarding.

My own stage 1 program has 10 functions, plus 5 more for testing, each 5 lines long on average

For example, you could begin by designing a function to extract the opcode from a byte, writing a test function for it, and adding a main program which calls the test function. Even though the opcode extraction function is probably only one line long, it is a line which is extremely error prone, so this approach will give you something robust and reliable to build on. Look at the bits chapter, or previous bits assignment, for bit manipulation info.

As well as bit manipulation, you are also going to need functions to read bytes from sketch files, and functions to make graphics calls. Many programmers get caught up in a mess of I/O straight away, with nothing being testable. To avoid that, the best advice is to add I/O last. Check the I/O chapter for how to read binary files.

You can process each byte one-by-one as they are read from the file, as if they were arriving in a stream from somewhere else. You only need a fairly small and fixed amount of information to keep track of the current state of the sketch.

You may choose to read the whole file into an array in memory. That isn't necessary, but it is reasonable. However, I would still recommend using a stream style, having a small fixed state and dealing with each byte from the array in turn.

You should be able to see from the description so far that you will need a state structure to hold the current position, whether the pen is up or down, the most recent DX value, and possibly the display object to draw on. You might also want to define some constants, e.g. DX for opcode 0 and so on.

As well as internal autotesting of your own functions, you need to use the external testing provided by the test.c module. The test.c module provides the same functions as display.c, but does no graphics. Instead, it just makes sure the calls you make are the ones expected. Use it by typing make test (or just make) instead of make sketch. Here is an example minimal program to illustrate how to do it:

#include "display.h"
int main(int n, char *args[n]) {
    if (n != 2) { fprintf(stdout, "Use ./sketch filename\n"); exit(1); }
    display *d = newDisplay(args[1], 200, 200);
    line(d, 30, 30, 60, 30);
    line(d, 60, 30, 60, 60);
    end(d);
}

The name of the sketch file should come from the command line (that's how I am going to be marking your program). So, you will type ./sketch lines.sketch.

The first argument to newDisplay must be the name of the sketch file such as lines.sketch, so that the test.c module can work out what calls to expect.

The two calls to line are the ones expected for lines.sketch. Try leaving one out, changing one, or adding another call, to see what feedback you get from test.c.

The end call tells test.c that the sketch is complete, so that it gives you a confirmation message that you have made all the expected calls.

Opcode 2 (which wasn't used in stage 1) represents a PR prefixing operation, for creating or extending operands. The state contains a current operand value under construction, and keeps track of whether the value has been initialized. Any op can be preceded by PR prefix ops.

In a sequence consisting of PR ops followed by DX or DY, the first op in the sequence initializes the value and establishes its first six bits, including its sign. Each further PR op and the final DX/DY op adds six more bits to the value.

For example, in the sequence PR a; PR b; DX c, the op PR a sets the value to signExtend(a), then PR b sets the value to (value << 6) | b and then DX c sets the value to (value << 6) | c. The DX op uses the final value as its operand, then resets the current value ready for the next op sequence.

Opcode 3 no longer means PEN. It now represents a DO operation, where the number in the remaining size bits, plus three, becomes the opcode. These ops have no direct operand within the instruction byte, but may be preceded by prefix ops to provide an operand. The extended opcodes supported are:

• Opcode 3 (DO 0 = 0xC0) represents PEN as before, so this is compatible with stage 1.
• Opcode 4 (DO 1 = 0xC1) represents a DT operation which causes a pause of a given number of milliseconds. This allows a sketch to become an animation, e.g. replaying a freehand sketch as it was originally drawn. If the operand of the DT operation is zero, that means to use the same value as the last time DT was used with an operand. That makes animations with a fixed rate very compact.
• Opcode 5 (DO 2 = 0xC2) represents a CLEAR operation which clears the graphics screen. This would be useful, for example, if there were an animation consisting of a series of sketches in a single file.
• Opcode 6 (DO 3 = 0xC3) represents a KEY operation in which the program waits until the user responds by pressing a key. It ignores which key is pressed. This would be useful, for example, if a sketch presented a question, then waited for a key press before revealing the answer. (For KEY to work, the user may need to click on the graphics window to make it active. The window's quit button can still be used while the program is waiting for a key press.)
• Opcode 7 (DO 4 = 0xC4) represents a COL operation which changes the current drawing colour. It takes a full 32-bit colour operand. The operand is in a packed RGBA format, with one unsigned byte each of red, green, blue, and opacity (alpha) components. Opacity 0 means fully transparent, 255 means fully opaque. The primary colours are red (0xFF0000FF), green (0x00FF00FF) and blue (0x0000FFFF), while black is 0x000000FF and white is 0xFFFFFFFF.

In a sequence PR a; PR b; DX c the operand is built up from a, b and c.

With an extended op, there are no operand bits in the byte itself. So, for example, in a sequence PR a; PR b; DT the operand to the DT op is just built from a and b (with no contribution from the DT byte).

If you are interested, this prefix scheme is partly inspired by the transputer instruction set and the UTF8 character encoding. It has several advantages over the more normal approach of having each op read its operand from bytes which follow.

• It allows ops to be variable-length without using bits to specify the length.
• For DX and DY, it is more compact for smallish operands because there is room for 6 bits of operand in the DX/DY byte.
• The ops don't have to be changed if the size of the integers used in the implementation changes.
• Each byte is completely self-contained and self-describing, and doesn't involve reading any more bytes, making the sequence of ops stream-like.
• The whole system is more testable.

As well as the current position, whether the pen is up or down, and the most recent DX value, the state now needs to store the most recent non-zero DT value, the current value of the operand under construction, and a flag to say whether that value has been initialized.

In the assembly language style of writing ops, we can now just write an opcode with an arbitrarily large operand. For example, DX 42 refers to the two bytes 80 2a. You could also write that as PR 0; DX -22. The zero prefix is needed to make sure the six bits in the DX op are treated as positive rather than negative.

The fact that prefixes are sometimes zero means that using "value == 0" as a test for the value being uninitialized doesn't work, even though an uninitialized value is implicitly zero. So a separate flag is recommended.