Basics of C/C++ Programming 2016

From EIK wiki

Introduction

This is a version of the course from autumn 2016. For current information see Basics_of_C/C++_Programming


Lecturers

Rait Liiv: rait.liiv@itcollege.ee

Janno Tomingas: janno.tomingas@itcollege.ee

C

Lectures

1. Week. Introduction to C and C++

https://echo360.e-ope.ee/ess/echo/presentation/854d0a23-530c-4b4e-a40a-94b4d613d0a1?ec=true

2. Week. Memory, pointers, datatypes

https://echo360.e-ope.ee/ess/echo/presentation/4c2fd365-3495-4175-a3cb-14b52a001e9e?ec=true

3. Week. Runtime, stack, heap (dynamic) memory, linker, declaration + definition

https://echo360.e-ope.ee/ess/echo/presentation/a4f70f62-3569-4abc-bf81-638ef9e0da7f?ec=true

4. Week. Stack, heap, pointer, jumps, typedef

https://echo360.e-ope.ee/ess/echo/presentation/8e0deb8d-ffab-4a0a-9456-78428674ccb3?ec=true

Practices

Practice 1

Console input/output


1. Write a program, that outputs "Hello, World!"

2. Write a program, that asks the user for a number and then writes the number back to the user

3. Write a simple calculator, that supports addition, subtraction, multiplication and division. The program should ask the user for two numbers and the operation to perform and output the result to the console.

Practice 2

Functions, pointers, out variables, function return values as success/error codes


1. Write a function that adds two integers, outputs the result via an out variable and returns 0 to indicate a successful operation.

Hint:

 int add(int a, int b, int* out)
 {
 }


2. Write a function that swaps two integers and returns 0 to indicate a successful operation.

Hint:

 int swap(int* a, int* b)
 {
 }


3. Write a function that reverses a string and returns 0 to indicate a successful operation.

Hint:

 int reverse(char* string, size_t length)
 {
 }


4. Write a function that sorts an array of ints and returns 0 to indicate a successful operation.

Hint:

 int sort(int* string, size_t length)
 {
 }


Practice 3

File input/output, dynamic memory allocation


1. Write a program that outputs the contents of a text file into the console.

Hint:

Always close the file stream after you are done using it.

Make sure to check for error codes.


2. Write a program that reads the contents of a text file into a dynamically sized array and outputs the information into a new file.

Hint:

Use "fseek", "ftell" and "rewind" to find out how large the buffer should be.

Make sure you have enough room for a null terminator.

Remember to free the allocated memory after calling malloc or calloc.

Make sure to check for error codes.


Practice 4

Dynamic memory allocation continued, structs, .h/.c files


1. Create an implementation of a stack data structure (Stack (abstract data type)) that uses a dynamically allocated array for storage.

  • Required functions:
    • init - Initializes stack's variables and allocates required dynamic memory with an initial(default) size,
    • destroy - Frees all allocated memory and optionally resets other stored information for a stack,
    • push - Adds an element to the top of the stack,
    • peek - Gets the top element of the stack,
    • pop - Gets and removes the top element of the stack;


  • Describe the stack struct and functions in a separate .h file,
  • Implement the functions in a corresponding .c file,
  • Test your stack with some operations. Remember to check for edge cases;
Hints:
  • How do you know which element to access?
  • How do you know if an array is full?
  • How should the functions behave when a stack is empty?
  • How should the functions behave when a stack is full?
  • What will happen if any of the functions are called unexpectedly many times?

Assignment

Write a program that reads values from a file and outputs the result to stdout.

Input

Input file's name is "input.txt".

The file contains index-value pairs of integers on a single line. Integers in a pair are separated with a comma (,) and pairs are separated with a semicolon (;).

All indices between 0 and (count_of_pairs - 1) are guaranteed to be present.

The indices are guaranteed to be unique.

The indices are not guaranteed to appear in an ascending order.

Sample input: 1,4;0,2;2,8

Output

The program should output the differences between consecutive values as the index increases.

Output should be printed as a comma separated list of values on a single line to stdout.

For input:

0,1;2,4;1,2

Calculates:

0,1 to 1,2 -> 2 - 1 = 1
1,2 to 2,4 -> 4 - 2 = 2

And outputs:

1,2
Examples
->
0,2 -> 0
1,2;0,1 -> 1
1,4;0,2;2,8 -> 2,4
1,4;0,2;2,-2 -> 2,-6

C++

Lectures C++

5, 6, 7 Week. C++, class, namespace, new + delete, reference, libraries, bool.

https://echo360.e-ope.ee/ess/echo/presentation/6b331ce5-dcc9-4bbf-a490-13d40bef2812?ec=true

https://echo360.e-ope.ee/ess/echo/presentation/4c009949-e8b4-43a0-adc0-8ed055baf7b9?ec=true

https://echo360.e-ope.ee/ess/echo/presentation/f994eebc-39c8-4ea8-8056-d358d89b329c?ec=true


8. Week. Const. + Additional leftover from previous lectures.

https://echo360.e-ope.ee/ess/echo/presentation/95e5962a-3d0b-489f-a759-86dd7a29f2ef?ec=true

9. Week. Templates

https://echo360.e-ope.ee/ess/echo/presentation/7f7c58b8-8173-42a4-8b9a-a3941196376a?ec=true

10. Week. Iterator, Casting,

https://echo360.e-ope.ee/ess/echo/presentation/bfec4cef-6c38-46c0-9e06-1da985d94a66?ec=true

11. Week. Static, Smart pointers, RAII

https://echo360.e-ope.ee/ess/echo/presentation/1b6f336e-52b8-4993-8c6f-de0cd5eb8a49?ec=true

12. Week. Exception, Assembly language

https://echo360.e-ope.ee/ess/echo/presentation/c093e098-f789-4600-8b5c-f7995b3abfcb?ec=true

Practices

Practice 1

Console input/output, strings, references, arrays, new/delete


1. Write a simple calculator, that takes a simple binary operation (+,-,*,/) as an input and outputs the result to the console on a new line.

Example:

 1 + 2 -> 3
 3 * 8 -> 24
2. Write a program that asks the user for several strings and outputs the total numbers of characters entered.
  • Ask for the number of strings the user will enter,
  • Store all input strings in in an appropriately sized array,
  • Use a function to count the total number of characters entered;

Example:

Input:

3
one
two
three

Output:

11
Practice 2

Classes, constructors/destructors, member functions, intro to templates, vector


1. Create a class Rectangle, that:

  • Stores the width and height as private member variables,
  • Uses a constructor to set width and height,
  • Has public member functions to calculate and return the area and circumference of the rectangle;


2. Create a program that uses std::vector to store several Rectangles and computes the total area of all stored rectangles.


3. Convert the stack (Practice 4 of C) from C to C++:

  • Replace the struct with a class,
  • Add member functions,
  • Make use of constructors and destructors,
  • Adjust member functions to return values on success (and, for the bold, throw on failure),
  • Use a class template to describe the datatype stored in the struct;
Practice 3

Inheritance, dynamic polymorphism, unique_ptr


1. Create classes Rectangle and Circle, that:

  • Store necessary data as private member variables,
  • Have a public member function to calculate and return their area;


2. Create a program, that:

  • Creates and stores some Rectangles and Circles,
  • Calculates the total area of the shapes;


3. Create a base class for previously created objects, called Shape:

  • Create a public virtual member function area,
  • Create a protected member variable to store the number of a Shape's corners in,
  • Modify both Rectangle and Circle to inherit Shape and override the virtual function,
  • Modify your program to store Shapes in a vector of unique pointers to Shape;

Sample code


4. Add a class Triangle, that inherits from Shape:

  • Store the necessary data,
  • Create the necessary functions,
  • Use all the Shapes in your program;


5. Add a function to calculate the Shapes' circumference.


6. (optional) Similarly to the Shapes, create a hierarchy of Animals, that:

  • Know their name,
  • Can write out the sound they make;

Use your Animals in a simple program.

Practice 4

Overloading, template functions, template classes


1. Create a new header file:

  • Create a function add - int add (int a, int b),
  • Create separate implementations of the add function for floats, doubles, and strings,
  • Try out the functions;


2. Template the add function.


3. Create a simple templated Queue (Queue (abstract data type)), that:

  • Uses a container to store the items in,
  • Has a member function to add items to the queue (enqueue),
  • Has a member function to get items from the queue (dequeue);


4. Create a template class Accumulator, that:

  • Stores an instance of the templated type as a member variable,
  • Sets the initial value of the variable via the constructor,
  • Has a member function to add to the stored value,
  • Has a member function to retrieve stored value;

You may assume the templated type is not a pointer and has operator+= defined.


5. (optional, self-research) Create a class Distance, that can be used with the Accumulator:

  • Store the value in a member variable,
  • Overload operator+= to support addition between two instances of the Distance class,

Additional information on operators and operator overloading can be found at operator overloading.


Practice 5

Function pointers, lambdas, std::function


1. Create a function that counts the number of odd numbers in a container of ints:

  • Implement the function,
  • Store the function pointer in a variable,
  • Use the function;


2. Create a lambda that returns the position of the first negative number in a container of ints:

  • Implement the lambda,
  • Store the lambda in a variable,
  • Use the lambda;


3. Create a lambda that calculates the factorial of an int:

  • Implement the lambda capturing the number by value,
  • Use the lambda;


4. Create a lambda that adds all non-negative numbers in a previously defined container of ints:

  • Implement the lambda capturing the container by reference,
  • Use the lambda;


5. Create a function zero_if, that:

  • Takes a reference to container of ints as its first argument,
  • Takes a comparison function as its second argument (has an integer as its parameter and returns a bool),
  • Returns void,
  • If the comparison function returns true for an int, sets its value to 0;

When zeroing all odd numbers in a vector

 [1, 2, 3, 4, 5]

The function should return

 [0, 2, 0, 4, 0]


6. Use the created function with newly created lambdas and functions. Sample usage might be to zero all negative integers in a vector.


Practice 6

STL Algorithms, lambdas in use


1. Find the largest element in a container of ints.


2. Sort a vector of ints using:

  • Sort the container into ascending order,
  • Provide a custom Compare function to sort the vector into descending order;


3. From a vector of ints remove all negative values (erase-remove):

  • Use std::remove_if to move all elements to be deleted to the end of the vector,
  • Use the vector erase method to delete all the elements from the vector;


4. From a vector of strings count the number of strings, that have a length greater than 5 characters.


5. From a vector of strings remove all strings that have a length under 3 characters.


6. Reverse all strings in a vector of strings.


Practice 7

Using external libraries


  • Download SFML and create a new project
Setting up the include and library directories:
Useful shorthand macros:
 $(SolutionDir) - Points to the directory where your solution file (.sln) is located
 $(ProjectDir) - Points to the directory where your project file (.vcxporoj) is located
 $(ENV_VAR) - Points to wherever a user variable or system variable points to, where ENV_VAR is the name of that variable

A full list of currently available environment variables can be found by pressing the "Macros>>" button when editing project include or library directories.

Include directories:
  • Make sure you have at least one .cpp file in your project.
  • Go to Project -> Properties -> C/C++ -> General.
  • Edit Additional Include Directories.
  • Add an entry that points to the SFML include directory.
  • If the previous steps were performed successfully, you should be able to include the SFML header files in your files (#include "SFML/Window.hpp")
Library directories:
  • Go to Project -> Properties -> Linker -> General.
  • Edit Additional Library Directories.
  • Add an entry that points to the SFML Libs/Release directory.
.lib files:
  • Go to Project -> Properties -> Linker -> Input.
  • For each SFML module that you use, add the required .lib files to the Additional Dependencies list (System.hpp requires sfml-system.lib). The dependencies for each module can be found at the SFML FAQs
.dll files:
  • For every .lib file that you use, find and copy the corresponding .dll file from the SFML/bin folder into the folder where your program's .exe file will be built to. (sfml-system.lib -> sfml-system-2.dll)
  • The default build target directory will be the Debug folder under your solution directory.


1. Create an empty window and an initial game loop.


2. Draw a white rectangle somewhere on the window.


3. Handle keyboard arrow events to move the rectangle around.


Create a simple snake game.


4. Simulate the movement of the snake:

  • Divide the window in a grid to help with movement and collision detection,
  • After each frame, draw a new rectangle to the right from the old one,
  • Make it possible to change the "moving" direction with arrow keys,
  • Do not let the rectangle leave the screen, have it wrap around to the opposite edge instead;


5. Add the tail:

  • Keep track of how long the snake should be,
  • Start with having one rectangle in a container (for example an std::deque),
  • Add the new rectangle (see part 4) to the start of the container each turn,
  • Remove the last rectangle once the tail grows too long;


6. Add collision checking:

  • Once the first rectangle (head of the snake) overlaps with either food or its tail, perform an action,
  • If the head overlaps with tail, end the game,
  • If the head overlaps with food, grow the tail;


7. Add food:

  • At the start of the game, spawn the food at a random unoccupied location on the screen,
  • When the snake eats the food, spawn more food;

Assignment

Implement Conway's Game of Life using C++ and SFML.

See Practice 7 for an example of how to set up the project.

General info

The game consists of a grid of cells. Each cell is either alive or dead. Every cell interacts with its eight adjacent cells.

Before the start of the game, the user can select which cells are alive or dead.

The user can not change the states of the cells while the automation is running.

Once the game is started, the states of the cells in the next frame are calculated for all cells in the grid based on the following rules:

  • If a live cell has fewer than two live neighbours, it dies,
  • If a live cell has two or three live neighbours, it lives,
  • If a live cell has more than five live neighbours, it dies,
  • If a dead cell has three live neighbours, it becomes alive;

The game calculates and displays new frames until the automation is stopped.

Example usage

The user starts up the program and selects some cells to be alive.

The user presses a key to start the game.

The automation runs until the user presses a key to end the game or closes the program.

Exploits

Lectures

12. Week. Exception, Assembly language

https://echo360.e-ope.ee/ess/echo/presentation/c093e098-f789-4600-8b5c-f7995b3abfcb?ec=true

13. Week. Discussion about vulnerabilities and exploiting.

https://echo360.e-ope.ee/ess/echo/presentation/e479b230-24a1-48d4-bbb1-a4621e1231ac?ec=true

Practices

Practice 1

Assembly language

Setting up your environment:

  • Create a new empty project,
  • Add a main.cpp file,
  • Under project "Properties -> C/C++ -> Code Generation" set Security Check to Disable Security Check;

To view disassembly:

  • While debugging your program, open the disassembly window at Debug -> Windows -> Disassembly;


2. Create an integer variable i:

  • Assign a value to i,
  • Add 1 to i,
  • Inspect the resulting assembly instructions;


3. Using what you have learned:

  • Create an integer variable a,
  • Using assembly, assign a value to a,
  • Using assembly, add 1 to a,
  • Verify, that the resulting value is correct;


4. Create a character array c to hold 3 characters:

  • Fill in the array one by one,
  • Inspect the resulting assembly instructions;


5. Using what you have learned:

  • Create a integer array d to hold 2 ints,
  • Using assembly, fill the array with data,
  • Verify, that the array is filled with expected values;


6. Create a simple if:

  • Subtract 1 from int i if i is equal to 2,
  • Inspect the resulting assembly instructions;


7. Using what you have learned:

  • Create an if conditional, that subtracts 1 from int a if int i and a are equal,
  • Verify, that the conditional works as expected;
Practice 2

Assembly language continued, stack smashing

1. Create a function that takes no arguments

  • Call the function
  • Inspect the resulting assembly instructions;


2. Using what you have learned:

  • Call the function using assembly,
  • Verify that the function gets called;


3. Create an add function:

  • The function should return the result of adding two integers passed in as parameters,
  • Call the function and store the result in a variable,
  • Inspect the resulting assembly instructions;


4. Using what you have learned:

  • Create a subtract function,
  • Use assembly to call the subtract function with different values and store the result in a variable,
  • Verify, that the function call works as expected and that the value gets stored;


5. Create a function that internally holds an array of only one void* and takes a void* as a parameter:

  • Write over the bounds of the array and observe what happens,
  • Try passing different pointers to the function;


Assignment

Do some research on vulnerabilities related to the following topics:

  • Buffer overflow (stack smashing, code injection, arc injection),
  • Arithmetic over-/underflow,
  • Memory leaks,
  • Double free (and double delete),
  • Formatted output,
  • Concurrency,
  • File I/O (symlinks, hardlinks);


Write an essay, that describes the causes, examples, and mitigation strategies for all of the topics.