20150928:Practical:C:Introduction

Introduction

The purpose of this first practical session is to take a first glance of C programming.

Using the shell in 2min

As you may have notice, you don't have fancy graphical interface installed on your session. Thus, you need to train yourself on using the UNIX environment and especially the shell.

The minimal commands you need are:

• ls: list directory content, without parameter it lists the content of the current dir
• cd: change directory, without parameter it brings you back to your home dir
• mkdir: create a directory
• cp: copy files/dirs
• mv: move/rename files/dirs
• rm: delete files/dirs
• rmdir: delete empty dirs
• pwd: where am I ?
• man: read the doc !
• apropos: which doc do I need ?
• info: more docs …

If you need more, the internet is full of tutorials, docs and other useful resources. I found this one recently (it's old but accurate): [1]

Compiling C code

In order to test compiling options and methods, we start with a pretty simple program:

/* hello.c */
# include <stdio.h>
# include <stdlib.h>
 
int main() {
  printf("Hello world !\n");
  return 0;
}

You can try to compile this code with a simple:

> gcc hello.c

It'll produce an executable file a.out which can be run using ./a.out in your shell. Of course, we have some options to pass to the compiler, so a more accurate version of this compilation line will be:

> gcc -Wall -Wextra -std=c99 -O2 -o hello hello.c

For more details about these options, refer to the lecture.

Since, our compilation line is pretty long, we want an automated way of compiling, for that we can use make.

> rm -f hello
> make hello
cc     hello.c   -o hello

As you can see make is able to compile your code without any configuration, but, we want it to use our options. We can obtain this by setting a minimal (and sufficient) Makefile:

# Basic Makefile
 
# Compilers and options
CC=gcc
CPPFLAGS=
CFLAGS= -Wall -Wextra -std=c99 -O2
LDFLAGS=
LDLIBS=
 
# END

Now we got:

> rm -f hello
> make hello
gcc -Wall -Wextra -std=c99 -O2    hello.c   -o hello

Advices for the rest of the subject

In the rest of this subject, we ask you to produce code in standalone files (a single file containing your code and a main to test it.) When a specific file is required for a question, there's a file name specification right after the title of the part. If there's no file name, it means that whether the part doesn't require a file to be written (like the example on how to get an integer from the command line) or you should continue using the same file as the previous part.

When we refer to a function name like this: printf(3), the (3) part indicate the section in the manual pages where you can find information about the given function. Most of the time it'll be section 3.

If you want information on the given function, you can invoke manual pages using the command man, like in the following example for printf(3):

shell> man 3 printf
PRINTF(3)               Linux Programmer's Manual              PRINTF(3)
...

Beware that, if you omit the section number (here 3), you may not get the page for C function, but (if it exists) the page for the command of the same name, like:

shell> man printf
PRINTF(1)                     User Commands                    PRINTF(1)
...

Finally, for most practical session, it's always a good idea to format a little bit your working directory, like this:

• 20150928_pratical/
  • AUTHORS
  • Makefile
  • C files required in the subject.

The directory name should reflect the corresponding practical session (look at the title) and corresponds to the standard date in the form: YYYYMMDD.

The authors file follow a standard form (used at EPITA, but not only):

shell> cat AUTHORS
* login_x
shell> cat -e AUTHORS
* login_x$

Test functions

We often use some standard function for testing, namely the following one:

# include <assert.h>
 
void assert(scalar expression);
 
# include <err.h>
 
void err(int eval, const char *fmt, ...);
void errx(int eval, const char *fmt, ...);
void warn(const char *fmt, ...);
void warnx(const char *fmt, ...);

• assert(3) is a macro that interrupt the program execution if the scalar expression is equal to 0.
• err(3) and errx(3) print on stderr the formatted message fmt(using printf(3) format) and interrupt the program, with eval as exit code. err(3) also print the error message corresponding to the current errno(3) value.
• warn(3) and warnx(3) print the same messages as err and errx but don't interrupt the program.

For more details, read the corresponding manual pages.

Command line

file name: cmdline.c

The purpose of this exercise is to inspect the command line of a program.

We want the following output:

shell> ./cmdline 
Command line length: 1
| ./cmdline |
shell> ./cmdline aa bb cc
Command line length: 4
| ./cmdline | aa | bb | cc |
shell> ./cmdline aa bb cc "dd ee"
Command line length: 5
| ./cmdline | aa | bb | cc | dd ee |

In order to print a string, you can use the following call to printf(3) where the variable str contains your string:

  printf("| %s ", str);

What you need to do is to iterate over the array argv from 0 to argc and print each entry in the array.

In order to display the length of the array (argc) you need the printf's format specifier %d (it's an int.)

Don't forget the last character on the line and the newline !

Using command line to get integer input

In the comming exercises, you'll need to take some input for the functions you'll write, a classical way of doing this is to:

• check if there's an argument (argc > 1 )
• convert the argument using strtoul(3)

Here is an example:

# include <err.h>
# include <stdio.h>
# include <stdlib.h>
 
int main(int argc, char *argv[]) {
  if (argc < 2)
    errx(2, "Usage:\n%s <number>", argv[0]);
  unsigned long        n;
  n = strtoul(argv[1], NULL, 10);
  printf("input: %lu\n", n);
  return 0;
}

For information on errx(3) check the man page !

Simple math functions

For the following exercises, you'll implement the some math functions and in order to test them, you'll build a main that get an integer from the command line and call the corresponding function.

Factorial

file name: fact.c

• Implement a factorial function

unsigned long fact(unsigned long n);

Remember, factorial is defined by:

fact(0) = 1
fact(n) = n * fact(n - 1)

Try to translate that using a loop !

Fibonacci

File name: fibo.c

• Implement the Fibonacci sequence

unsigned long fibo(unsigned long n);

Remember, Fibonacci is defined by:

fibo(0) = 0
fibo(1) = 1
fibo(n) = fibo(n - 1) + fibo(n - 2)

Like for fact, try to use loop !

Computing square root

File name: sqrt.c

We now want to implement an integer square root function, that is a function my_sqrt(n) that returns an integer verifying the following property:

my_sqrt(n) * my_sqrt(n) <= n < (my_sqrt(n) + 1) * (my_sqrt(n) + 1)

Heron method

We'll use the Heron method (related to Newton method) based on the following idea:

We choose a first approximation y such that n/y <= y <= n
While y > n/y:
  replace y by the mean between y and n/y
return y

The simplest initial value for y is n itself.

• Implement the sqare function

unsigned long my_sqrt(unsigned long n);

• Bonus: find a better starting approximation

Testing square root

In order to test square root, we'll try a more formal method. First, we can compute a series of perfect square numbers by getting a random number and raise it to its square. The following function perform a series of test, it fails using assert(3) if the result is not the expected one.

static
void testing_square(unsigned long len) {
  printf("Testing with perfect square:\n");
  for (unsigned long i = 0; i < len; i += 1) {
    unsigned long      n = random() % (1lu << 60),  r;
    r = my_sqrt(n * n);
    printf("\tmy_sqrt(%lu) = %lu - expected: %lu\n", n * n, r, n);
    // If incorrect, exit with an assertion error
    assert(r == n);
  }
}

Note: we use the POSIX random function, random(3), that is supposed to have a better enthropy than the libC's rand(3), but in order to use it, you need to add a feature_test_macro(7) at the begining of the file, before any header includes:

# define _XOPEN_SOURCE 500

Anyway, this test is not sufficient, it only tests sqare numbers. If we want to a more accurate test, we need a valid way of testing the square root of any number.

But, remember, our square root has a strong property:

my_sqrt(n) * my_sqrt(n) <= n < (my_sqrt(n) + 1) * (my_sqrt(n) + 1)

We can implement a test function that validate the output of our function.

• Implement the following function that validate the square root result:

int validate_sqrt(unsigned long n, unsigned long r);

The function should return 0 (false) if r is not a valid integer square root for n and a non-zero (true) value otherwise.

You can now write a function on the model of testing_square that test your square root with a series of random numbers.

• Implement the following function:

void testing_random(unsigned long len);

Finally you can group all this together in a program that: take a number of tests to be performed on the command line and run the two test functions with an output similar to this:

shell> make sqrt
gcc -Wall -Wextra -std=c99 -O2    sqrt.c   -o sqrt
shell> ./sqrt 10
Testing with perfect square:
	my_sqrt(3255460177606520689) = 1804289383 - expected: 1804289383
	my_sqrt(717291925660744996) = 846930886 - expected: 846930886
	my_sqrt(2828090596213971729) = 1681692777 - expected: 1681692777
	my_sqrt(2939979750280717225) = 1714636915 - expected: 1714636915
	my_sqrt(3832776420996370849) = 1957747793 - expected: 1957747793
	my_sqrt(179978164883572225) = 424238335 - expected: 424238335
	my_sqrt(518234968976368996) = 719885386 - expected: 719885386
	my_sqrt(2721709680964082064) = 1649760492 - expected: 1649760492
	my_sqrt(355832112534189201) = 596516649 - expected: 596516649
	my_sqrt(1415246710558899241) = 1189641421 - expected: 1189641421

Testing with random numbers:
	my_sqrt(1025202362) = 32018
	my_sqrt(1350490027) = 36749
	my_sqrt(783368690) = 27988
	my_sqrt(1102520059) = 33204
	my_sqrt(2044897763) = 45220
	my_sqrt(1967513926) = 44356
	my_sqrt(1365180540) = 36948
	my_sqrt(1540383426) = 39247
	my_sqrt(304089172) = 17438
	my_sqrt(1303455736) = 36103