Creative Commons License

Summary: Pointers

You can get address of an object using address operator, &. This address is a pointer to the pointed object. For example:

1
2
3
4
int var;
int *pointer;
pointer = &var;
int var2 = *pointer;

The data type of a pointer depends on the type of pointed object, even though pointer content is just an address. Above example shows type declaration of a pointer to an integer (int *). The above example sets pointer to refer to variable var.

The value behind a pointer can be accessed using an indirection (or derefencing) operator, *. When this operator is applied to an object, its data type changes from the original pointer to the type of the pointed object, in above example back to int.

It can be thought that the dereference operator and address operator are opposites: address operator (&) adds one star to the data type, while dereference operator (*) drops one star from the data type of the object.

Pointers can be chained: it is possible to have a pointer to a pointer to an integer. The data type of such pointer is then int**.

When declaring data types, int var, int var and int * var are equivalent -- there can be whitespace on either side of the pointer operator.

Pointteriluntti is a nice summary in Finnish about the necessities in pointers.

Pointer basics were discussed in Module 2.

Summary: Arrays

Array is a sequence of objects of certain type in consecutive locations in memory. Array can be defined as static, such as in the following for 5-element array: int array[5]; or using a pointer, in which case the array needs to be allocated separately (e.g., using malloc): int *array2;. In the latter case, the pointer typically points to the first element of the array. Array can be easily assigned to pointer variable: array2 = array; after which pointer points to first element of array.

A single array member can be accessed using the index operator: a[2] = 10; sets the third array member to 10 (as integer type). Array indexing starts from 0. Index operator can also be applied to pointer of same type, and it works similarly to a dereference (*) operator, but applied to indicated array element. Like deference, index operator "drops" one star from the data type:

1
2
3
int array[5];
int *array2 = array;
int a = array2[1];

The address operator can be applied also together with array indexing: int *pa = &array[1]; makes pointer pa refer to the second array element.

More information about arrays can be found in Module 2.

Summary: Strings

A common special case of array are strings, character arrays that end in 0 as the last character. C supports special syntax for declaring strings inside quotes:

1
char str[10] = "a string";

This effectively adds the terminating nil character automatically to the end of the string. The 0 character always uses one element in the char array, which should be considered when allocating space for a string. When a string is constructed from individual characters, the terminating nil needs to be added separately.

When string is not placed in an array, as above, it is allocated as a constant string, like this: char *str = "a string";. Modifying such string is not possible, and results in a run-time error. Therefore it usually better to use the const qualifier with such strings, to make the compiler notify about illegal use of the string: const char *str = "a string";.

There are several helpful functions for operating with strings, as defined in the strings.h header. A commonly used one is strlen that returns the number of characters in a string (without the terminating nil). strlen should not be confused with the sizeof qualifier that returns the size of a given data type.

Module 2 discussed about strings and string handling functions.

Task 01_polisher: Code polisher (3 pts)

Objective: Refresh your skills with string manipulation.

Implement "code polisher" for C that removes comments and sets the line indentation correctly based on program blocks.

a) Read file

Implement function char *read_file(const char *filename) that reads the the given file into dynamically allocated memory. The function returns a pointer to a string containing the file contents, or NULL if opening the file fails.

b) Remove comments

Implement function char *remove_comments(char *input) that removes C comments from program stored at input. Note that input points to dynamically allocated memory, for example as allocated in Task 6.1.a. The function returns pointer to the polished program. You may allocate a new memory block for the output, or modify the content directly in the input buffer.

You'll need to process two types of comments:

  • Traditional block comments delimited by /* and */. These comments may span multiple lines. You should remove only characters starting from /* and ending to */ and for example leave any following newlines untouched.

  • Line comments starting with // until the newline character. In this case also the newline character is removed.

The calling code is responsible only for the pointer returned by the function: if you allocate a new buffer for the output, you'll need to release the input buffer before returning from the function.

c) Indent code

(Note: This may be more difficult than the above two parts. If there are difficulties, it may be a good strategy to try other exercises and come back to this later)

Implement function char *indent(char *input, const char *pad) that adds proper indentation to the code given in buffer input. The style of one level of indentation is given in string pad: it could be, for example four space characters or a tab character, or something else. For each level of indentation, one sequence of pad string should be added before the actual line content. Any possible existing indentation in the original file (i.e., space or tab characters before first non-space character) should be ignored and all indentation should be done using the string specified by the pad string.

You can assume that only compound blocks are used: any { in code increases the indentation level by one, and any } in code decreases the indentation level by one, and no other indentation rules are applied. Identation starts after the opening curly brace, and ends before the closing curly brace.

As with the above case, if you allocate a separate buffer for output, you'll need to release the original input buffer before returning from the function (i.e., the caller assumes it is responsible only for the returned pointer). Note that because of indentation, the output may need more memory than input. Therefore, watch your use of memory, reallocate as needed.

Below is an example of code in 'src/testifile.c' processed by the function (with four spaces as 'pad'). As always, it is recommended that you test the function using the src/main executable, with different files, before submitting your solution to TMC.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
// This is a test file
int main(void) {
    /* comment
    block */
    printf("juu\n");
    while (1)
    {
        // Another comment
        while (2) {
            printf("jaa\n");
        }
    }
}

Summary: Memory Management

(Module 3)

Oftentimes memory needs to be allocated dynamically from heap, for example when the amount of needed memory is not known at the time of writing the program (e.g., depends on user input), or when a memory block needs to be shared between functions. malloc call is used for dynamic memory allocation. The malloc function takes the amount of needed bytes as parameter, and returns pointer to the allocated memory block, if it succeeds.

1
2
char *buffer = malloc(1000);
if (buffer == NULL) { /* allocation failed */ }

realloc function can be used resize an earlier allocated memory block.

When allocating memory dynamically, awarness of needed space is important. The sizeof operator that tells the size of a data type is often needed for determining the required space. When allocating an array, the space needed is the size of one array element (determined by sizeof), multiplied by the number or elements.

1
float *array = malloc(sizeof(float) * 10); // array of 10 float numbers

Dynamically allocated memory needs to be freed when not needed anymore, to avoid unnecessary use of system resources. Valgrind is a useful (and by now, familiar) tool that checks various memory handling issues, including leaks of unreleased memory.

Summary: Structures

(Module 3)

Structures are compound data types that consist of multiple fields of different data types that typically relate to each other in some way. Structure members can be any any other data type, such as pointers, arrays, or other structures. Here is an example of defining a structure:

1
2
3
4
5
struct example {
    int value;  // single integer
    char string[20];  // character array of 20 characters
    struct other *ptr;  // pointer to another structure
};

When structure is used as a basic data type, its members are accessed with the member operator (.). When using a pointer to structure, the structure members are accessed using structure pointer operator (->). Note that selection of either one of these operators depends on whether structure itself is pointer or not, regardless of the types of the structure members. Therefore, the following code is correct:

1
2
3
4
5
struct example ex1;
ex1.ptr = NULL;

struct example *ex2 = &ex1; // make ex2 point to ex1
ex2->ptr = NULL;

Task 02_parser: Command line parser (2 pts)

Objective: Get familiar with command line arguments, and refresh your memory on linked lists.

Command line arguments are a common way to give parameters for a program. A short summary of command line arguments and typical use of command line options was given in Module 4. We will now practice parsing the options given from the command line.

Your code will read the command line options and store them in a linked list of struct option structures. In this exercise command line options start with '-', and are followed by alphabetical character. Command line option may have an optional argument (string), which is in the following element of the argv array if it does not begin with the '-' character that identifies a new option. Each option can only have at most a single argument. If an argv member is not an option or its argument, it should be ignored. You will need to store the possible option argument in a new struct option field that you will add to the structure.

struct option is not complete: it is missing the space for option argument, so you will need to expand the structure. The structure contains place for the option character and the next pointer to implement a linked list. Do not modify these fields. Module 3 explained linked lists, if you need a refresher on them.

a) Parse options

Implement function get_options that will process the command line arguments given to function, and return a pointer to the start of linked list that contains the options. Each option on the command line (and its optional argument) will be a separate node in the linked list.

You will also need to implement function free_options that releases the dynamic memory allocated for the linked list.

b) Query options

Implement function is_option that will return non-zero if the given option character is in the options list, or zero if the option character could not be found.

Also implement function get_optarg that returns the option argument if one was provided with the given option. If the option was not given, or if it did not have an argument, the function returns NULL.

src/main.c demonstrates how these functions are used, assuming that you execute it from command line, giving some arguments. If you do not want to use the command line terminal, you will need to modify the main function to provide a test sequence of command line arguments.

Summary: Formatted I/O

printf function can be used for providing formatted output, using format conversion specifications. The use of printf, and most common format specifiers were listed in Module 1, so here we will just give a few examples:

1
2
3
printf("Reserve 10 characters on screen for string (left aligned): %-10s\n", string);
printf("float with 5 digits, one decimal: %5.1f\n", fl_var);
printf("unsigned long integer: %lu\n", sizeof(fl_var));</pre>

scanf is used for querying input from user, based on similar format specifiers than printf. The scanf parameters are pointers to the variables to be modified, because otherwise modifying them would not be possible.

printf and scanf, like all I/O, is buffered. For output in small programs (as in this course) buffering may not have visible effects in most cases, except for scanf that delivers the data only after a full line of input is given.

Task 06_election: Election system (2 pts)

Objective: Refresh on file handling, dynamic arrays with structures, and use of algorithms.

Implement an election system that calculates votes from given file. The system consists of two functions as follows:

a) read_votes that reads votes from given text file. Vote consists a name of no more than 39 characters, each given in a separate line. See file src/votes.txt for a short example. Based on the votes you should build a dynamic array where each element is a votes structure. Each name in the file should be represented only once in the array, and associated with the count of how many times that name was represented in file. In other words, the array has as many elements as the file has different names. The end of the array is indicated by an additional element that has empty string as a name. For example with the example file the array will have four elements, plus the ending element. This array is returned to the caller.

Note that the names should not include the newline character that separates the votes in the file.

b) results that outputs the results of voting, using the created dynamic array, in the screen in the following format:

name: votes

The results should be ordered based on the number of votes, having the entry with most votes first. In cases where there are same number of votes, the names are ordered according to alphabetical order. Remember that C library contains handy helper functions for easy ordering of data.

For example, the main.c function should output the following with given src/votes.txt:

Trump: 4
Clinton: 2
Sanders: 2
Cruz: 1

(The example is purely fictional.)

Feel free to generate your own test files when developing the functions. Implement functions to file election.c based on the definitions in election.h.

Summary: Bitwise operations

More extensive coverage of bitwise operations is given in Module 4, but here is a quick summary:

Result of bitwise AND (&) has bits set only if corresponding bits are set on both sides of the AND operator. This can be used, for example, for testing a condition for certain bits (or bit mask). For example:

1
if (val & 0x10)  { /* fifth bit is set */ }

Result of bitwise OR (|) has bits set if corresponding bits are set on either side of the OR operator. This can be used for combining two bit sets -- simple addition cannot be used, as it may have wrong result. For example:

1
int combined = 0xf1 | 0x03; // result: 0xf3

Bit shift operations (<< and >>) transform bit pattern a given steps to either direction. These may be useful sometimes.

It is important to notice the difference between bitwise AND (&) and OR (|) operations and logical AND (&&) and OR (||) operations. Compiler does not warn about them, because both could be valid (it does not know), but logical and bitwise operations have different result.

Task 03_mac: MAC header (2 pts)

Objective: Refresh your memory on how bitwise operations worked.

Low-level protocol headers often try to make good use of every available bit, for efficient use of the communication medium. This time we will focus on the 802.11 MAC header (i.e., Wi-Fi), and specifically the first two octets in it, on the "Frame Control" part.

The 802.11 header structure is illustrated here, for example (there are also many other related resources in the web). The Frame Control fields are illustrated in the diagram labeled "3.3" further down on the page. You will need this diagram to be able to parse the different Frame Control fields, as needed in this exercise.

a) Parse header

Implement the following functions, that each read one header field from the MAC header. To parse the fields, you will need to pick the respective bits from the header, and possible apply bitwise shift, to make the resulting values match what is given below.

  • get_proto_version that will return the protocol version from the header (should return integer values 0-3)

  • get_type that will return the frame type (integer values 0-3)

  • get_subtype that will return frame subtype (integer values 0-15)

  • get_to_ds, get_from_ds, get_retry, get_more_data that will return these respective flags from header. Any non-zero value will be considered as set flag, and zero value means an unset flag.

b) Set header

Implement the following functions for setting the header:

  • set_proto_version that will set the protocol version header field according to the version argument in the function.

  • set_type that will set the type field according to the type argument in the function

  • set_subtype that will set the subtype field according to the subtype argument in the function

  • set_to_ds, set_from_ds, set_retry, set_more_data that will set the respective flags according to the flag argument in the functions. If the flag argument is non-zero, the flag bit will be set, if it is zero, the flag bit will be cleared.

The set_* functions should only modify the particular bits in the header, and the other fields in the header must not be modified by the functions.

Task 04_dungeon: Dungeon game (5 pts)

The recent history knows a class of terminal-based dungeon crawling games such as Rogue, Nethack and Angband. Unfortunately, development of many of the original games has ceased by now, but this exercise tries to revive this magnificient traditional class of games.

This exercise implements a simple poor man's version of a dungeon crawling game. As you will notice, it lacks several features compared to its original predecessors, but you are free to enhance the game in various ways you like.

The exercise template contains more code than the earlier exercises so far. Many of the function implementations are already given, and you only need to implement functions identified in below subtasks. There are following source files under the src directory of the task template:

  • main.c contains the main loop that asks a command from user, and triggers actions for the user's character and the monsters in the game.

  • mapgen.c generates the dungeon, including rooms and corridors between them.

  • userif.c contains functions related to interacting with the user: showing the visible sections of map, and acting on the user input. In the current configuration, player can see five squares far (pretty short-sighted game character), and (naturally) cannot see behind walls, but you can change these parameters if you want.

  • monster.c has the logic for monsters on the game: the game is turn-based: after each player movement, all monsters on the map are moved, based on the algorithms that you will implement. Most of the functions you need to implement for this exercise are in this file.

  • dungeon.h contains definitions (e.g., structures) and needed public function prototypes. The header does not contain all functions: functions that are private to a particular module, are not included.

The game uses a few main data structures: Game contains the main game state, and links to different components, such as two-dimensional map array, or dynamically allocated array of monsters. The game structure also contains the player character information. Map holds the pointer to two-dimensional map. This map is allocated such that the vertical dimension (mapHeight elements) is the first array, consisting of the rows of mapWidth elements. Creature contains information of one monster, and the Game structure contains a dynamically allocated array of these, with numMonsters indicating the number of Creature elements in the array.

Additional information can be found embedded with the source code, such as descriptions of the functions. You can modify the code as you like: add new kinds of monsters, change the way the map is presented, add different types of characteristics for the monsters and the player, and so on, as long as you don't modify or remove the existing fields, that may be used by the TMC tests. The TMC tests only focus on certain functions, as identified below. Everything else is free for you to change.

The game is played by running the src/main executable in the source directory. It won't be very interesting nor work correctly, though, before you have implemented the functions described in below tasks.

Below is a screenshot of a game after all tasks below have been implemented (Monster 'D' approaching character '*' from left). Current (and max) hitpoints are shown above the command prompt.

    ...    
   ##.##   
   #...#   
   #...#  #
####...##..
..D..*.....
###########



HP: 12(12)
command >

Currently the game has the following commands:

  • n: move north
  • s: move south
  • e: move east
  • w: move west
  • q: exit game

Input is line buffered, so you'll need to press enter after the command. You can change or redo the command processing, if you wish -- TMC tests will not care about that.

Many tests assume map as saved in file test/testmap, for example when testing monster movement. It is not advisable to modify this file: that might affect the outcome of local tests, but won't change the result of server-side tests.

a) Blocked position

Implement function int isBlocked(Game *game, int x, int y) that returns 0, if the given position on map is unoccupied: it is not wall, and is not occupied by a monster. Otherwise, the function returns a non-zero value. The function should also return non-zero value if the given coordinates are out of bounds of the map. This function will be useful helper in many of the other functions described below. The function placeholder can be found in userif.c

b) Create monsters

Implement function void createMonsters(Game *game) that creates opts.numMonsters monsters, and places them on random positions in game area (use rand() function to generate random numbers). The monsters must be placed on free positions that are not wall, and not occupied by other monsters [e.g., !isBlocked(..)]. Initialize also other monster details, such as name, the map sign shown on user interface, hitpoints, and so on. Each monster must have more than 0 hitpoints, and initial HP needs to be same as the maximum HP. Otherwise you can choose the monster details as you will (for example, to contain random values), but name must be set, and map sign must be an alphabetic character.

c) Move Towards

Implement function void moveTowards(Game game, Creature monst) that moves monster monst one step towards player's character. The default game logic uses this function to make the monsters move towards the character, unless they are low on hitpoints. The test will check the following:

  • If possible, the distance between monster and the character must reduce as a result of this call

  • The monster must not move more than one step on the map at a time

  • The monster must not move over wall

  • The monster must not move to same location with another monster

  • The monster must not move to same location with the character

Within these restrictions, you can implement your movement algorithm as you will. You can assume that monsters have magical powers to detect the player character's location irrespective of the walls.

d) Move Away

Implement function void moveAway(Game game, Creature monst) that moves monster monst one step away from player's character. The default game logic invokes this behavior when monster is low on the hit points. The test will check the following:

  • If possible, the distance between monster and the character must increase as a result of this call

  • The monster must not move more than one step on the map at a time

  • The monster must not move over wall

  • The monster must not move to same location with another monster

  • The monster must not move to same location with the character

Within these restrictions, you can implement your movement algorithm as you will.

e) Monster action

void monsterAction(Game *game) is the function that will invoke an action for every monster still alive in the game. For each monster, if monster is in adjacent location with the character, it should try to attack the character. Otherwise, the monster should invoke the movement action (for example, moveTowards or moveAway). If monster is dead (HP==0 or less), no action is taken.

Function pointers attack and move in Creature structure determine the action to be taken. Use these functions to invoke either of these monster actions, following the above logic. If either of the function pointers is NULL, the respective action is ignored.

Note that you should have specified valid attack and movement behaviors (i.e., function pointers) when creating monsters. The game template provides one attack behavior, but you can define more as you will