Shell

• The bash guide for beginners of the the linux documentation project
• An introduction to shell commands (source) by Victor Gedris
• Some lecture notes to complete the previous document

Text manipulations

• We first want to keep only the odd lines of the following text:

Je suis très émue de vous dire que j'ai
bien compris l'autre soir que vous aviez
toujours une envie folle de me faire
danser. Je garde le souvenir de votre
baiser et je voudrais bien que ce soit
là une preuve que je puisse être aimée
par vous. Je suis prête à vous montrer mon
affection toute désintéressée et sans cal-
cul, et si vous voulez me voir aussi
vous dévoiler sans artifice mon âme
toute nue, venez me faire une visite.
Nous causerons en amis, franchement.
Je vous prouverai que je suis la femme
sincère, capable de vous offrir l'affection
la plus profonde comme la plus étroite
en amitié, en un mot la meilleure preuve
dont vous puissiez rêver, puisque votre
âme est libre. Pensez que la solitude où j'ha-
bite est bien longue, bien dure et souvent
difficile. Ainsi en y songeant j'ai l'âme
grosse. Accourrez donc vite et venez me la
faire oublier par l'amour où je veux me
mettre.

To do that, you can use the following guide:
• Save this text in a file
• Use the command nl to number the lines of the file
• As we are only interested in the parity of the line, we only care of the last digit of each number ; remove the useless column with the function colrm
• Use the command grep to keep only the odd lines.
• Remove the useless columns to print the result
• Do the same process by using only a one line command (you'll need to use the pipe | character)
Correction:
$ nl Sand.msg | colrm 1 5 | grep [13579] | colrm 1 2
• The answer from Musset was an acrostic you get the meaning by reading the first word of each line:

Quand je mets à vos pieds un éternel hommage
Voulez - vous qu'un instant je change de visage ?
Vous avez capturé les sentiments d'un cour
Que pour vous adorer forma le Créateur.
Je vous chéris, amour, et ma plume en délire
Couche sur le papier ce que je n'ose dire.
Avec soin, de mes vers lisez les premiers mots
Vous saurez quel remède apporter à mes maux.
Bien à vous, Eric Jarrigeon

The answer of Sand was on the same kind:

Cette insigne faveur que votre cœur réclame
Nuit à ma renommée et répugne à mon âme.

After saving these two texts in separated files, first create files containing only the first column of each answer ; this can be done with the cut function (for instance, one can use " " as a delimiter, and take only the first field). Then, create a single file containing these two columns written in two separated line. Finally, make the whole operations in a single line (the function echo, with the correct option, may help).
Correction:
$ echo -e `cut -d" " -f1 Musset.rep` "\n"`cut -d" " -f1 Sand.rep`

Around the find function

• Use the command wget to get the file arbre_phylogenetique.tar.bz2 that you can find at the urlhttp://www.lifl.fr/~poteaux/fichiers/phylogenetic-tree.tar.bz2 in the repertory of your choice.
• What is the size of this file ?
• Uncompress the file by using the command bunzip2.
• What is the size of the file you get ?
• This is an archive file. You need to extract it by using the tar command.
• Find the file charlie_01.txt in the tree by using the command find, read it, and follow the instructions inside.
Correction:
Once inside the racine directory, $ less `find -name charlie_01.txt` $ less `find -name lisezmoi.txt* ! -empty` $ less `find ! -name lisezmoi.txt ! -name charlie_01.txt -type f` $ find -type f -exec rm {} \;
• Now that you know a little more what is inside the original tree, do you see a way to find all the necessary files in only one search ?
Correction:
Once inside the racine directory, $ less `find -type f ! -empty`

A few scripts

• Without using $@, $* or $#, write a script that print all its parameters line by line
Correction:
#! /bin/sh while [ -n "$1" ]; do echo $1 shift done
• Write a script that print the files inside a given directory line by line, with the type of the file written before (on a separated line). The script must test if there is a single parameter and that it is indeed a directory ; if not, this must print how to use the function
Correction:
#! /bin/sh usage() # How to use this script { echo "Usage: `basename $0` directory" echo "Print the files inside directory and their type" echo "Must have a single parameter which must be a directory". return 0 # exit status of the function } if [ $# -eq 1 -a -d $1 ] then for i in `ls $1` ; do file -b $1/$i echo $i done else usage fi
• Write a script that copy all the files with the extension .txt in a repertory given as an input, and that replace the extension by .old
Correction:
#!/bin/bash usage() # How to use this script { echo "Usage: `basename $0` directory path1/file1.txt ... pathN/fileN.txt" echo "Copy the N files in directory, with an extension .old (file1.old ... fileN.old)" echo "First argument must be a directory. If a file does not have a .txt extension, it is ignored". return 0 # exit status of the function } if [ -d $1 ] # test if the first parameter is a directory then DIR=$1 shift # we now consider only the files for i in "$@" ; do if [ ${i##*.} != "txt" ] then usage else cp $i $DIR/`basename $i .txt`.old # here we use the basename function and not something like {$i%.txt} # in order not to have a problem with the path of the new name fi done else usage fi

Creation of a trash

• Create the command can, that will accept 3 options:
  • can -l list the trash;
  • can -r purge the trash;
  • can filenames send filenames to the trash;
• Add the option can -x filenames that remove directly the files filenames, without going through the trash (the command shift may help)

Getting informations on the memory

• Write a script memtot that compute the sum in kilobytes of the memory used by the user's process
Correction:
#!/bin/bash # memtot # A variable that contains the result SUM=0 for i in `ps ux | cut -c26-31` do SUM=$(( SUM + i )) done echo $SUM
• Write a script topuser that print the user taking the most CPU ; we will consider the round part of each percentage only
Correction:
#!/bin/bash MAX=0 for i in `ps aux | tail -n +2 | cut -f1 -d' ' | sort | uniq` do SOMCPU=0 for CPU in `ps aux | tail -n +2 | grep $i | cut -c16-19` do CPU=${CPU%.*} SOMCPU=$(( SOMCPU + CPU )) done if [ $SOMCPU -gt $MAX ] then MAX=$SOMCPU MAXUSER=$i fi done echo "$MAXUSER utilise environ $MAX pour cent du CPU"

Generating files

• Write a script that, given a file cmd.ext (ext can be any extension name) containing shell commands outputs a text file out.ext that contains the commands we would get. For instance, if one runs this script on a file cmd.txt that contains: A=4 echo A echo $A B=5 expr A+B one should create a file out.txt like that: $ A=4 $ echo A A $ echo $A 4 $ B=5 $ expr A+B A+B
• Try your script for these commands: ls thisfiledoesnotexist echo $? Run also them on a shell. Do you get the same result ? Why ? How to correct this ?
Correction:
This answer is given in two files, but this is obviously not mandatory. #!/bin/bash # generateExec.sh RET=0 # the option -r for the command read is used to desactivate the interpretaiton of the \ while read -r line; do if ! echo "$line" | grep -q "^[ ]*$"; then if echo "$line" | grep -q "^#"; then echo "$line" else echo "$ $line" # this enables to get the old $? (exit $RET) eval $line RET=$? fi; fi; done exit 0 #!/bin/bash #generateAll.sh for FIC in cmd.*[^~]; do OUT=`echo $FIC | sed -e s/^cmd/out/` echo "$FIC -> $OUT" rm -f $OUT ./generateExec.sh < $FIC > $OUT 2>&1 if [[ "$?" -ne "0" ]]; then echo "Error on $FIC"; exit 1 fi; done

C

• Some lecture notes (work in progress, that will be updated quite often)

First programs

• Write a program that read two integers and print their gcd.
Correction:
# include <stdio.h> main() { int a,b,r; printf("Entrez a "); scanf("%d",&a); printf("Entrez b "); scanf("%d",&b); while ((r = (a % b)) != 0) { a = b; b = r; } printf( "Le pgcd est %d\n",b); }
• The hamming weight of a number is the number of non zero bytes its binary form contains.
  • Write a program that computes the Hamming weight of an integer (type int) in a number of operations proportional to the size of the input.
  Correction:
  # include <stdio.h> main() { int n,s,weight = 0; printf("Write an integer "); scanf("%d",&n); for (s=n; s > 0; s>>=1) weight+=y&1; printf("The Hamming weight of %d is %d\n",n,weight); }
  • How to get a number of operations proportional to the Hamming weight of the input ?
  Correction:
  # include <stdio.h> main() { int n,s,weight = 0; printf("Write an integer "); scanf("%d",&n); s=n; while (n != 0) { weight++; n = n & ( n - 1 ); } printf("The Hamming weight of %d is %d\n",s,weight); }
• What does the following code ? main(){int x,p=0;scanf("%lu",&x);for(;x>0;p++) x&=x-1;printf("%d\n",p);}
  Correction:

  This computes the Hamming weight of a given integer. Here, the stdio library is not declared, but this still compiles correctly because it is automatically checked by the preprocessor nowdays. The scanned number (%lu) is not declared as an integer but as an unsigned long, but this is also interpreted quite well. Therefore, this program works and gives the expected result. But writing it as in the previous question is definitely more than welcomed.
• Write a program that, given a value x with type double, computes the evaluation of the polynomial P(X)=a_n Xⁿ + ... + a₁ X + a₀ at X=x. The degree n, the coefficients a_i and x will be inputed by the keyboard. To compute the evaluation of the polynomial, we will use the Horner scheme (we first compute a_n x + a_n-1, then a_n x²+a_n-1x + a_n-2 ...).
  Correction:

  # include <stdio.h> main() { int n,i; float res,a,x; printf("Degree of the polynomial ? "); scanf("%d",&n); printf("Value of x ? "); scanf("%f",&x); for( i = n ; i >= 0 ; i--) { printf("Give the coefficient of index %d\n",i); scanf("%f",&a); if (i==n) res = a; else res=res*x+a; } printf("The value of the polynomial in x=%f is %f\n",x,res); }

Plotting time computations

• This exercise will use several intermediary functions. Therefore, we are going to separate them and use header files. To be able to test the intermediary functions one by one, we will use a menu. During this exercise, you will modify the following code so that you can run the different functions you will create.
  File menu.h:

  /* The first two lines and the last one are made so that the preprocessor will read this file only once */ # ifndef MENU_H # define MENU_H /* we include the standard libraries we will use */ # include <stdio.h> /* for printf and scanf */ # include <stdlib.h> /* for exit(), EXIT_SUCCESS and EXIT_FAILURE */ /* we include the other files related to this one */ # include "fact.h" /* one can define some constants */ # define CONSTANT 12 /* we declare the functions */ extern void menu(); # endif /* MENU_H */
  File menu.c:

  # include "menu.h" void menu() { printf("menu :\n"); printf("1 - Compute a power of a value\n"); printf("2 - Compute a factorial\n"); printf("3 - exit\n"); } int main(void){ int n,k; float x; /* one may want to add a loop here */ menu(); scanf("%d",&n); switch (n) { case 1: { printf("Value of x ? "); scanf("%f",&x); printf("Value of n ? "); scanf("%d",&k); printf("Not implemented yet"); /* printf("%f",power(x,k)) */ break; } case 2: { printf("Value of n ? "); scanf("%d",&k); printf("Not implemented yet"); /* printf("%d",fact(k)) */ break; } case 3: { printf("Good bye\n"); break; } default: { printf("Sorry, this option does not exist\n"); exit(EXIT_FAILURE); } } exit(EXIT_SUCCESS); }
  To compile a code that is separated in several files, one can run the following command: $ gcc mainfile.c secondaryfile1.c secondaryfile2.c secondaryfile3.c More generally, we will use a makefile to manage the compilation.
• Preliminary functions:
  • Write a function factorial, that given an integer n, compute n!. We will use a recursive algorithm.
    Correction:

    int fact(int n)
    {
      return n<=1 ? 1 : n*fact(n-1);
    }		
    	                

  • Write a function power, that given a value x and an integer n, compute xⁿ. We will use an iterative algorithm.
    Correction:

    float power(float x, int n)
    {
      float res=1;
      while (n>=1)
        { 
          res*=x;
          n--;
        }
      return res;
    }
    	                

• Write a function that reads a value x and an integer n, and returns the evaluation at x of the truncated Taylor series at order n. For instance, if one gives x=.12 and n=1, this will return 1.12. For this first program, we will use the functions power and fact of the two previous questions.
Correction:

File exp_basic.h:

# ifndef EXP_BASIC_H
# define EXP_BASIC_H

# include "fact.h"
# include "power.h"

extern float exp_basic(float, int);

# endif /* EXP_BASIC_H */
			

File exp_basic.c:

# include "exp_basic.h"

float exp_basic(float x, int n){
  float res=1;
  int i;
  for (i=1; i<=n; i++)
    res+=power(x,i)/fact(i);
  return res;
}

• Try it for x=20, and for increasing order of truncations (for instance, for 12, 20, 30 and 40). What happens ? Can you explain such results ?
Correction:

For the first values, one get the correct mathematical approximation. But at some point (normally 13), the result is not good anymore; and for higher value, one get negative values, and then inf (which means infinit), and sometimes nan (which means "not a number"). One can check that by running the factorial function for n=12, 13 and some higher values. Same for the power function, for instance for x=20 and n=29 and 30.

• Without changing the algorithm, what can be changed to solve the matter ?
  Correction:

  The "problem" comes from the representation of the numbers on the computer: an integer is (usually) stored on 32 bytes. As 13! is greater than 2³². Therefore, when trying to represent if, the first byte of 13 is lost, and we do not get the correct result. To solve that matter, one can compute the factorial as a float, or better again a long double (same for the power function).

• We will now consider the running time of this program. To do that, one may adapt the following code to our context: # include <time.h> ... clock_t initial_time; /* Initial time in micro-seconds */ clock_t final_time; /* Final time in micro-seconds */ float cpu_time; /* Total time in seconds */ ... initial_time=clock(); fct (); final_time=clock(); cpu_time=(final_time - initial_time)*1e-6; printf ("%f",cpu_time);
  • Modify the menu so that one option computes an approximation of an exponential, and also gives the running time of this computation.
  • To plot the time computations, we will use the gnuplot function. This enables to display data contained in a file. Discrete data contained in a columns of a file example.dat will be used in the following way: the command

    plot "example.dat" i j title 'example'

    will plot the data of the i-th (as abscissa) and j-th (as ordinate) columns. Columns must be separated by a space ; lines beggining by # are ignored. Create (in a separate file) a c program that computes an approximation of exp(3) with an approximation order of 2^k, k=1..14, and print the running time for these computation on the screen, together with the corresponding approximation order.
    Correction:

    File time1.h: # ifndef TIME1_H # define TIME1_H # include <stdio.h> /* for printf and scanf */ # include <stdlib.h> /* for exit(), EXIT_SUCCESS and EXIT_FAILURE */ # include <time.h> /* to manage the running times */ # include "exp_basic.h" clock_t initial_time; /* Initial time in micro-seconds */ clock_t final_time; /* Final time in micro-seconds */ float cpu_time; /* Total time in seconds */ # endif /* TIME1_H */ File time1.c:

    # include "time1.h"
    
    int main()
    {
      int i,j=1;
      long double res;
      for (i=0; i<=14; i++)
        {
          initial_time=clock();
          res=exp_basic2(3,j);
          final_time=clock();
          cpu_time=(final_time - initial_time)*1e-6;
          printf("%d %Lf %f\n",i,res,cpu_time);
          j<<=1;
        }
      exit(EXIT_SUCCESS);
    }

  • Store these data in a file time1.dat, and use the gnuplot function to plot them. One could use a file containing the following lines as an input to the function gnuplot:

    set term postscript landscape
    set output "timeall.ps"
    plot "time1.dat" using 1:2 title 'basic algorithm'
    		  

    (the first two lines are only usefull if one want to store the plotting).
• One can see that the approximation order we can use is not very high in practice. Find a new clever algorithm to compute the Taylor series, and generate some timings for the computation of exp(3) with an approximation order of 2^k, k=1..24. Plot the result together with the previous running time from the naive algorithm.
  Correction:

  File exp_better.h: # ifndef EXP_BETTER_H # define EXP_BETTER_H extern long double exp_better(long double, int); # endif /* EXP_BETTER_H */ File exp_better.c:

  # include "exp_better.h"
  
  float exp_better2(float x, int n){
    float res=1,c=x;
    int i;
    for (i=2; i<=n+1; i++)
      {
        res+=c;
        c*=(x/i);
      }
    return res;
  }

  File time2.h: # ifndef TIME2_H # define TIME2_H # include <stdio.h> /* for printf and scanf */ # include <stdlib.h> /* for exit(), EXIT_SUCCESS and EXIT_FAILURE */ # include <time.h> /* to manage the running times */ # include "exp_better.h" clock_t initial_time; /* Initial time in micro-seconds */ clock_t final_time; /* Final time in micro-seconds */ float cpu_time; /* Total time in seconds */ # endif /* TIME2_H */ File time2.c:

  # include "time2.h"
  
  int main()
  {
    int i,j=1;
    long double res;
    for (i=0; i<=24; i++)
      {
        initial_time=clock();
        res=exp_better(3,j);
        final_time=clock();
        cpu_time=(final_time - initial_time)*1e-6;
        printf("%d %Lf %f\n",i,res,cpu_time);
        j<<=1;
      }
    exit(EXIT_SUCCESS);
  }

All programs for this exercise:

You can find here ($ wget http://www.lifl.fr/~poteaux/fichiers/exponential.tar.gz is another way to get it) an archive containing all the programs for this exercise, given with a makefile. You can extract it via the tar command ($ tar -xzf exponential.tar.gz). Then, you can use the $ make command to see how to create the executive files, or also directly the plot files. In particular, you can have a look at the makefile to see that it is not used only to compile the c programs.

The GDB debugger

# define len 10

int main ()
{
  int tab[len];
  unsigned int i;

  for (i=len-1; i>=0; i--)
    tab[i]=i;
  return 0;
}
	  

• By reading it, what do you think this code does ? Compile it and run the executable. What's happening ?
• To understang what's going on, we will use the debugger gdb. To use it, we need to add the option -g of gcc when compiling. Then one runs $ gdb executable_name. One can also use the command M-x gdb of Emacs. This leads to the gdb prompt:

  		(gdb)
  	      

  Here are some gdb commands we can use at this point:
  • (gdb) run (shortcut r) runs the executable,
  • (gdb) print i (shortcut p) prints the variable i,
  • (gdb) display i prints the value of i at each step used,
  • (gdb) whatis M gives the type of the variable M,
  • (gdb) call function(arguments) prints the result of the function call for given values,
  • (gdb) break 9 (shortcut b) makes a break when reaching the line 9 of the program. One can add conditions to the break command (for instance, (gdb) break 9 if i=0 || j != 3),
  • (gdb) b file.c:9 makes a break when reaching the line 9 of file.c,
  • (gdb) continue (shortcut c) run the program up to the next break,
  • (gdb) next (shortcut n) enables to run a program step by step after reaching a break,
  • (gdb) quit (shortcut q) quits gdb.
  Run gdb and follow the variable i. When i reachs 0, what happens next ? Why ?
• How to solve the problem ?
  Correction:

  By running gdb, one can see that the segmentation fault appears at the line 9 (tab[i]=i;). One can put a break here (b 9), follow the variable i (display i), and run the program again (r or run), and continue step by step (continue or c each time). This enables us to see that the value i goes from 0 to 4294967295. This is because i is an unsigned it. To solve the problem, we just need to declare i as an int.

Sorting a table

 srand((unsigned int) time(NULL));

The algorithm should print something like:

 Initial table
23 51 26 34 15

Sorted table
15 23 26 34 51

# ifndef SORT_H
# define SORT_H

extern void swap (int[], int, int);
extern void insertion_sort(int[], int);
extern void quicksort(int[], int, int);

# endif /* SORT_H */

Numerical computations

• Without using any computer: does the following program compile ? If yes, do you think hat the executable will work correctly ? To do what ?

  int main()
  {
    float x=1;
    while (x!=x+1)
      x=x+1;
    return 0;
  }
  	      

  Correction:
  This is indeed an algorithm: the while loop will end, because at some point, the value of x will be big enough so that x=x+1. One can see that into practice by running the following algorithm: # include <stdio.h> int main() { float x=14000000000000000000.1; while (x != (x+1)) { x=x+100000000000000000.1; printf("%f\n",x); } return 0; }