20151005:Practical:C:SDL:Arrays

Introduction

This session will introduce some array manipulations and simple image loading and manipulation using the SDL library.

GIT set-up

GIT provides mechanism to keep track of versions of files and synchronization between copies of the same source tree. Basic operations you need to know are how to submit (commit) your changes, how to push your changes to a server and how to pull new version from a server.

Setting the environment

There's a file containing global configuration for GIT in your home directory. The file ~/.gitconfig will hold basic settings like your name, email address and global options. Here is an example of this configuration file:

[user]
	name = John Simth
	email = john.simth@epita.fr
[color]
	ui = true
[push]
	default = simple

SSH Key

One way to authenticate on a git server is to use ssh, most of the time using a public/private keys pair. If you haven't generate such a keys pair, here is a simple way to do it:

> ssh-keygen -t rsa -b 4096 -f ~/.ssh/my_git_key_file
Generating public/private rsa key pair.
Enter passphrase (empty for no passphrase):
Enter same passphrase again:
Your identification has been saved in /home/login/.ssh/my_git_key_file.
Your public key has been saved in /home/login/.ssh/my_git_key_file.pub.
The key fingerprint is:
[ ... snip ... ]

Be sure that the directory ~/.ssh has been created before.

The public key that you will provides for the ACU intranet (providing authentification for git) will be my_git_key_file.pub.

You can add login information for the ACU's GIT services inside the file ~/.ssh/config:

Host git.acu.epita.fr
User git
IdentityFile ~/.ssh/my_git_key_file

You can now upload the key to the ACU's intranet [1] (deploy the menu under the login, and use the link related to ssh keys and follow the instructions.)

Cloning a repository

Now, you can clone praticals' repository to start-up working, go to a working directory of your own, and then use git clone:

> git clone git@git.acu.epita.fr:s3-tuto-2019/login-s3-tuto.git

You have two repositories:

• one for all the practical session (git@git.acu.epita.fr:s3-tuto-2019/login-s3-tuto)
• one for the project (git@git.acu.epita.fr:s3-projects-2019/login-s3-projects) where login is the login of the group leader

Remarque: any members of the group is able to clone and/or update the project repository, you don't need to be the project leader.

Now we can do simple manipulations:

> cd login-s3-tuto
> mkdir 20151005_practical
> cd 20151005_practical
> echo '* login' > AUTHORS
> git add AUTHORS
> git commit -m "Initial commit"
> git push -u origin master

OK, first lines are obvious. In the fourth line, we add AUTHORS to the list of tracked files, then in the fourth line we commit the change with a simple message and finally we push the change to the server (specifying that we want the distant server called origin to be the default for push/pull.)

Basic Commands

Now you can try to edit in an other place the repository and synchronize your first version.

For example, if you have already cloned the repository and made pushed some modification from another copy, you can update the local version:

> cd login-s3-tuto
> git pull --rebase

You can check the status of tracked files and unadded files using git status and then add modified or newly created files:

> git status
status output
> git add my_modified_file.c my_new_file.c
> git commit -m "some message explaining what I've done."
> git push

If you need help on git, you can use inline docs:

> git help
...
> git help add
...
> man 7 giteveryday
...
> man 7 gitcore-tutorial
...

Or dig a little bit in git documentations here:

• http://git-scm.com/documentation
• http://git-scm.com/docs/gittutorial
• https://www.atlassian.com/git/tutorials/

Ignore binary files

You should avoid pushing binary files in your repository, in particular you must not add .o files.

One of the simplest way to avoid adding files you don't want is to set-up a file called .gitignore. This file can live in the root of your repo or in any sub-directories (in this case, its effect is limited to the corresponding sub-dirs.) The format of the file is pretty simple: each line is a pattern for reject files (using classical regexp), here is a simple example:

*.o
*~
*.tar
*.tar.gz
*.tar.bz2
*.tgz

The first pattern *.o reject all object code produced by the compiler, the second one reject emacs' backup files, and the remaining lines reject several form of tar archives (compressed or not.)

You can set-up an ignore file for all your practical sessions:

> cd login-s3-tuto
> cat .gitignore
*.o
*~
*.tar
*.tar.gz
*.tar.bz2
*.tgz
> git add .gitignore
> git commit -m "Adding a gitignore file."
> git push

Arrays

The following serie of exercises introduces basic array manipulation.

Your goal is to complete the following litle program:

# define _XOPEN_SOURCE 500
 
# include <assert.h>
# include <err.h>
# include <stdio.h>
# include <stdlib.h>
 
/* Provided code for testing and inspiration */
 
static inline
void swap(int *a, int *b) {
  int c = *a;
  *a = *b;
  *b = c;
}
 
 
static
void fill_array(int arr[], size_t len) {
  for (size_t i = 0; i < len; i++)
    arr[i] = random() % 1000;
}
 
static
void print_array(int arr[], size_t len) {
  for (size_t i = 0; i < len; i++) {
    printf("| %3d ", arr[i]);
  }
  printf("|\n");
}
 
/**********************************/
/* Code to be completed		  */
/* See subject for specifications */
/**********************************/
 
int* min_pos(int arr[], size_t len) {
  /* FIX ME */
}
 
void select_sort(int arr[], size_t len) {
  /* FIX ME */
}
 
int is_sorted(int arr[], size_t len) {
  /* FIX ME */
}
 
/* entry point */
 
int main(int argc, char *argv[]) {
  // Need a length
  if (argc < 2)
    errx(1, "missing array len");
  size_t len = strtoul(argv[1], NULL, 10);
  // Create and fill array
  int *arr = malloc(len * sizeof (int));
  fill_array(arr, len);
  // Print the array
  print_array(arr, len);
 
  // Sort array using your code
  select_sort(arr, len);
 
  // Print it again
  print_array(arr, len);
 
  // Assertion: verify that array is sorted
  assert(is_sorted(arr, len));
  return 0;
}

Finding minimal element

• Implement the following function:

int* min_pos(int arr[], size_t len);

This function looks for the cell containing the minimal value in the array arr of length len and returns a pointer to the cell.

You can get the address of a cell using either &(arr[i]) or arr + i.

Selection sort

• Implement the following function:

void select_sort(int arr[], size_t len);

This function implements the selection sort algorithm, that can be described as follow:

select_sort(tab, len):
  for i = 0 to len - 2 do
    min = find position of minimal in tab
    swap tab[i] and tab[min]
  done

Of course, you can use the functions swap (provided) and the function min_pos of the previous function.

Testing sorted array

• Implement the following function:

int is_sorted(int arr[], size_t len);

This function returns true (not 0), if the array arr of length len is sorted in increasing order and false (0) otherwise.

Using SDL

Checking for the libs

Check if you got all you need: pkg-config give you option for your compiler, among which you'll find the installation path of the lib. You should get similar input to mine:

> pkg-config --cflags sdl
-D_GNU_SOURCE=1 -D_REENTRANT -I/usr/include/SDL 
> ls /usr/include/SDL/SDL.h /usr/include/SDL/SDL_image.h
/usr/include/SDL/SDL.h  /usr/include/SDL/SDL_image.h

Simple Makefile

Here is a simple Makefile for the exercises using SDL:

## Simple SDL mini code
 
CC=clang
 
CPPFLAGS= `pkg-config --cflags sdl`
CFLAGS= -Wall -Wextra -Werror -std=c99 -O3
LDFLAGS=
LDLIBS= `pkg-config --libs sdl` -lSDL_image
 
SRC= pixel_operations.c main.c
OBJ= ${SRC:.c=.o}
 
all: main
 
main: ${OBJ}
 
clean:
	rm -f *~ *.o
	rm -f main
 
# END

Start-up code

First, we need to init SDL, open a window, load an image, display it and wait for a pressed key. This part of the code is not really interesting, I'll just give the code with some comments.

Waiting for a key:

void wait_for_keypressed(void) {
  SDL_Event             event;
  // Infinite loop, waiting for event
  for (;;) {
    // Take an event
    SDL_PollEvent( &event );
    // Switch on event type
    switch (event.type) {
    // Someone pressed a key -> leave the function
    case SDL_KEYDOWN: return;
    default: break;
    }
  // Loop until we got the expected event
  }
}

Initializing SDL:

void init_sdl(void) {
  // Init only the video part
  if( SDL_Init(SDL_INIT_VIDEO)==-1 ) {
    // If it fails, die with an error message
    errx(1,"Could not initialize SDL: %s.\n", SDL_GetError());
  }
  // We don't really need a function for that ...
}

Loading an image from a file:

SDL_Surface* load_image(char *path) {
  SDL_Surface          *img;
  // Load an image using SDL_image with format detection
  img = IMG_Load(path);
  if (!img)
    // If it fails, die with an error message
    errx(3, "can't load %s: %s", path, IMG_GetError());
  return img;
}

Now, we can write a function that take the surface corresponding to a loaded image and open a window with the same dimension, display the image on it and wait for a key:

SDL_Surface* display_image(SDL_Surface *img) {
  SDL_Surface          *screen;
  // Set the window to the same size as the image
  screen = SDL_SetVideoMode(img->w, img->h, 0, SDL_SWSURFACE|SDL_ANYFORMAT);
  if ( screen == NULL ) {
    // error management
    errx(1, "Couldn't set %dx%d video mode: %s\n",
         img->w, img->h, SDL_GetError());
  }
 
  /* Blit onto the screen surface */
  if(SDL_BlitSurface(img, NULL, screen, NULL) < 0)
    warnx("BlitSurface error: %s\n", SDL_GetError());
 
  // Update the screen
  SDL_UpdateRect(screen, 0, 0, img->w, img->h);
 
  // wait for a key
  wait_for_keypressed();
 
  // return the screen for further uses
  return screen;
}

Once you're finished with your image, you should free it using SDL_FreeSurface().

• Put everything into a file main.c add the headers SDL/SDL.h and SDL/SDL_image.h and write the main function.

Pixel operations

These functions, derived from SDL documentation, are used to get a pixel value or to set it in a surface. They manage all image formats and return a unified type for a pixel that can be used with SDL_GetRGB and SDL_MapRGB to map the pixel to RGB component.

First, the header:

// pixel_operations.h
 
# ifndef PIXEL_OPERATIONS_H_
# define PIXEL_OPERATIONS_H_
 
# include <stdlib.h>
# include <SDL.h>
 
Uint32 getpixel(SDL_Surface *surface, unsigned x, unsigned y);
void putpixel(SDL_Surface *surface, unsigned x, unsigned y, Uint32 pixel);
 
# endif

Then the code:

// pixel_operations.c
 
// Simple get/put pixel for SDL
// Inspired by code from SDL documentation
// (http://www.libsdl.org/release/SDL-1.2.15/docs/html/guidevideo.html)
 
# include "pixel_operations.h"
 
static inline
Uint8* pixelref(SDL_Surface *surf, unsigned x, unsigned y) {
  int bpp = surf->format->BytesPerPixel;
  return (Uint8*)surf->pixels + y * surf->pitch + x * bpp;
}
 
Uint32 getpixel(SDL_Surface *surface, unsigned x, unsigned y) {
  Uint8 *p = pixelref(surface, x, y);
  switch(surface->format->BytesPerPixel) {
  case 1:
    return *p;
  case 2:
    return *(Uint16 *)p;
  case 3:
    if(SDL_BYTEORDER == SDL_BIG_ENDIAN)
      return p[0] << 16 | p[1] << 8 | p[2];
    else
      return p[0] | p[1] << 8 | p[2] << 16;
  case 4:
    return *(Uint32 *)p;
  }
  return 0;
}
 
void putpixel(SDL_Surface *surface, unsigned x, unsigned y, Uint32 pixel) {
  Uint8 *p = pixelref(surface, x, y);
  switch(surface->format->BytesPerPixel) {
  case 1:
    *p = pixel;
    break;
  case 2:
    *(Uint16 *)p = pixel;
    break;
  case 3:
    if(SDL_BYTEORDER == SDL_BIG_ENDIAN) {
      p[0] = (pixel >> 16) & 0xff;
      p[1] = (pixel >> 8) & 0xff;
      p[2] = pixel & 0xff;
    } else {
      p[0] = pixel & 0xff;
      p[1] = (pixel >> 8) & 0xff;
      p[2] = (pixel >> 16) & 0xff;
    }
    break;
  case 4:
    *(Uint32 *)p = pixel;
    break;
  }
}

Converting an image to grey level

As an application will now iterate over the image in order to transform it into a grey image. Our conversion will use one of the classical conversion based on luminance definition. The basic version compute the average of the RGB components and then set all component to this value. While this is supposed to be correct, human perception of colors are slightly different: green appears brighter than red which is also brighter than blue. Thus, we'll compute a pondered average using the following coefficient: 0.3 for red, 0.59 for green and 0.11 for blue.

In order to convert the image you first need to be able to convert a given pixel:

• from the Uint32 pixel value, you can obtain three Uint8 value using SDL_GetRGB(pixel, img->format, &r, &g, &b) where pixel is the pixel value, img is the surface corresponding to your image and r, g, b are three Uint8 variable that will contains the RGB components.
• Using the previous coefficients compute the average value for the luminance (using a floating point variable to store the result)
• Set r, g, b to the luminance
• Get the new pixel value with SDL_MapRGB(img->format, r, g, b)

Once ready, you need to iterate over the pixel of the image: the surface provides img->w which is the width of the image and img->h which the height, just need a double for loop, the get and put pixel operations and this is it.

• Extend the previous code (in main.c) so that after displaying the original image, it transforms the surface in grey level and blit it (take a look at the provided code) to the screen once again, then wait for a key and leave.