システムプログラミング序論演習

演習6：関数ポインタ，エラーとエラー処理

例題1：多くの分岐先に分岐するプログラム

このプログラムはコマンドラインの第1引数に曜日を表す数を受け取り，それに対応する曜日の英単語を表示するプログラムである．
- 0と7が日曜日，1が月曜日，2が火曜日，．．．，6が土曜日を表すとする．
- 0から7の範囲の外の数が与えられた場合にはエラーメッセージを表示する．

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
  int n;

  if (argc != 2) {
    fprintf(stderr, "Missing argument\n");
    exit(1);
  }

  n = atoi(argv[1]);

  switch (n) {
  case 1:
    printf("Monday\n");
    break;
  case 2:
    printf("Tuesday\n");
    break;
  case 3:
    printf("Wednesday\n");
    break;
  case 4:
    printf("Thursday\n");
    break;
  case 5:
    printf("Friday\n");
    break;
  case 6:
    printf("Saturday\n");
    break;
  case 0:
  case 7:
    printf("Sunday\n");
    break;
  default:
    fprintf(stderr, "Invalid argument: %d\n", n);
    exit(1);
  }

  return 0;
}

このプログラムをファイルに保存し，そのファイルを gcc コマンドでコンパイルしなさい．
できた実行型ファイルを，0から7までの整数のどれかを引数に与えて実行し，その整数に相当する曜日が表示されることを確認しなさい．また，それ以外の整数を引数に与えて実行し，エラーメッセージが表示されることを確認しなさい．

課題1

コマンドラインの第1引数に21以上99以下の整数を受け取り，それに対応する英単語を表示するプログラムを作成しなさい．このプログラムは，たとえば，引数に 45 が与えられたら forty five を表示し，80 が与えられたら eighty を表示する．

このプログラムは英単語の行だけ（1行だけ）を出力する．行末には改行を入れる．

10の桁を表す英単語と1の桁を表す英単語は1個の空白で区切ること．それらの間にハイフンを入れたり，それらをくっつけたりしてはいけない．

英単語の後，かつ，改行の前の部分に，空白が入っていてもよい．

例題2：関数ポインタを用いたプログラム

このプログラムは引数で指定されたファイルの内容を読み込み，読んだ値のリストを作成する．次に，関数ポインタで指定される様々な関数をリストの各要素に対して実行し，その結果を表示する．
- ファイルの先頭行にはリストの要素の数を示す整数が書かれているものとする．
- 以降の行にはリストの各要素を示す整数が1行に1個ずつ書かれているものとする．
- このプログラムはリストの全要素のうち，以下の各基準で最も評価が高い要素を表示する．各基準での評価は，それぞれ，id, num_of_divisors, sum_of_digitsで計算されている．
  - 値が大きければ大きいほど評価が高い
  - 約数の数が多ければ多いほど評価が高い
  - 各桁の数の和が大きければ大きいほど評価が高い
- さらに，このプログラムはリストの全要素に対して以下の操作を適用する．
  - 各要素の値に1を足す
  - 各要素の値の符号を反転する
  - 各要素の値を3倍にする
  - 各要素の値の符号を再度反転する
  - 各要素の値を，偶数なら0に，奇数なら1に変える
- map_func（未実装）は，引数に受け取った関数をリストの全要素に適用する関数である．
- choose_best（未実装）は，引数に受け取った関数によってリストの各要素の評価を計算し，最も評価が高い要素（評価結果の値ではない）を返す関数である．評価結果の値が同じである要素が複数ある場合には，要素そのものの値が最も大きいものを返す．
- map_func と choose_best が未実装であるために，現状では，このプログラムは正しく動作しない．

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct record {
  int number;
  struct record *next;
};

struct record *head = NULL;

void insert_list(int num)
{
  struct record *cell;
  cell = (struct record *)malloc(sizeof(struct record));
  if (cell == NULL) {
    perror("malloc");
    exit(1);
  }
  cell->number = num;
  cell->next = head;
  head = cell;
}

void print_list(void)
{
  struct record *p;
  printf("[");
  for (p = head; p != NULL; p = p->next) {
    if (p != head) {
      printf(", ");
    }
    printf("%d", p->number);
  }
  printf("]\n");
}

int add1(int n)
{
  return n + 1;
}

int neg(int n)
{
  return -n;
}

int mul3(int n)
{
  return n * 3;
}

int is_odd(int n)
{
  if (n % 2 == 0) {
    return 0;
  } else {
    return 1;
  }
}

int num_of_divisors(int x)
{
  int i;
  int count = 0;
  for (i = 2; i <= x / 2; i++) {
    if (x % i == 0) {
      count++;
    }
  }
  return count + 1;
}

int id(int x)
{
  return x;
}
  
int sum_of_digits(int x)
{
  int sum = 0;
  while (x > 0) {
    sum += x % 10;
    x = x / 10;
  }
  return sum;
}

void map_func(int (*f)(int))
{
  /* not yet implemented */
  return;	  
}
	  
int choose_best(int (*f)(int))
{
  /* not yet implemented */
  return 0;
}

int main(int argc, char *argv[])
{
  FILE *fp;
  int nlines, i, num;
  char buf[256];

  if (argc != 2) {
    fprintf(stderr, "Missing file argument\n");
    exit(1);
  }

  if ((fp = fopen(argv[1], "r")) == NULL) {
    perror("fopen");					
    fprintf(stderr, "File: %s\n", argv[1]);
    exit(1);
  }

  if (fgets(buf, sizeof(buf), fp) == NULL) {
    fprintf(stderr, "Can't read input data\n");
    exit(1);
  }
  if (sscanf(buf, "%d", &nlines) != 1) {
    fprintf(stderr, "Can't read number of items\n");
    exit(1);
  }

  for (i = 0; i < nlines; i++) {
    if (fgets(buf, sizeof(buf), fp) == NULL) {
      fprintf(stderr, "Can't read input data\n");
      exit(1);
    }
    if (sscanf(buf, "%d", &num) != 1) {
      fprintf(stderr, "Can't read data item\n");
      exit(1);
    }
    insert_list(num);
  }

  fclose(fp);

  print_list();

  printf("Best value under standard 1: %d\n", choose_best(id));
  printf("best value under standard 2: %d\n", choose_best(num_of_divisors));
  printf("best value under standard 3: %d\n", choose_best(sum_of_digits));

  map_func(add1);
  print_list();

  map_func(neg);
  print_list();

  map_func(mul3);
  print_list();

  map_func(neg);
  print_list();

  map_func(is_odd);
  print_list();

  return 0;
}

課題2

map_func と choose_best を完成させて，プログラムを完成しなさい．プログラムの実行ファイル名は ex6_2 とする．入力としてファイル ex6_data.txt を与えて ./ex6_2 ./ex6_data.txt を実行し，プログラムが正しく動くことを確認すること．

例題3：メモリアクセスのエラーを含ませやすいプログラム

このプログラムは3つの文字列と1つの整数の中身を端末（標準出力）に出力するプログラムである． 3つの文字列はそれぞれbuf1, buf2, buf3に格納されている．整数はzに格納されている．このプログラムはまずそれらを出力した後に，端末（標準入力）からユーザの入力を受け付ける．その後，2つ目の文字列をユーザの入力した文字列で置換した上で，同じ内容を出力する．
このプログラムは深刻な欠陥を含んでいる．このプログラムは，ユーザが短い文字列を入力している限りにおいては，確保されたメモリ領域の範囲外にアクセスすることはない．しかし，長い文字列を入力すると，そのようなアクセスが起こりうる．

#include <stdio.h>
#include <string.h>

void replace_message(char *buf)
{
  char input[256];
  if (fgets(input, 256, stdin) == NULL) {
    return;
  }
  strcpy(buf, input);
}

int main(void)
{
  char buf1[10], buf2[10], buf3[10];
  int z = 0x12345678;

  strcpy(buf1, "Hello\n");
  strcpy(buf2, "safe\n");
  strcpy(buf3, "world\n");

  printf("%s", buf1);
  printf("%s", buf2);
  printf("%s", buf3);
  printf("Your ID=0x%08x\n", z);

  printf("Input? ");
  fflush(stdout);
  replace_message(buf2);

  printf("%s", buf1);
  printf("%s", buf2);
  printf("%s", buf3);
  printf("Your ID=0x%08x\n", z);

  return 0;
}

このプログラムをファイルに保存し，そのファイルを gcc コマンドでコンパイルしなさい．
できた実行型プログラムをコマンドライン引数なしで実行しなさい．
プログラムに入力を聞かれるので，適当な文字列（例えば unsafe）を入力しなさい．
そのプログラムが，以下のように，一部の文字列を入力文字列で置き換えた文字列を出力することを確認しなさい．

$ gcc -Wall -o ex6_3 ex6_3.c
$ ./ex6_3
Hello
safe
world
Your ID=0x12345678
Input? unsafe
Hello
unsafe
world
Your ID=0x12345678
$

課題3

このプログラムに対して攻撃用の文字列を入力し，Your ID=0x12345678 が表示されていた場所に Your ID=0x44556677 が表示されるようにしなさい．すなわち，このプログラムの内部の変数を不正に書き換えなさい．修正後のプログラムの実行では，それ以外の部分の出力はどうなっていてもよいし，異常終了してもよい．この課題ではプログラムを提出する必要はない．攻撃用の文字列を与えたときの実行結果を提出しなさい．プログラムの実行ファイル名は ex6_3 とする．

注意：情報科学類計算機室の端末の Mac 環境では，コンパイラに防御機構が備わっているため，この課題を解くことは難しい．この課題については Mac 端末で Linux を起動して使うか，viola12.coins.tsukuba.ac.jp などの Linux サーバの環境を使ってほしい．全学計算機システムの Linux 環境を用いて課題を解いてもよい． Mac 端末上の Linux 環境や全学計算機システムの Linux 環境でもコンパイラに防御機構が備わっているが，コンパイラに -fno-stack-protector というオプションを与えれば，その機構をオフにすることができる．
ヒント：まずは，すごく長い文字列を与えてみて，結果を見てみよう．
ヒント： ASCII in Wikipedia
余談：この課題には直接関係しないかもしれないが，プログラム（プロセス）のどのアドレス範囲が有効であるか，アクセスできるかを簡単に調べる方法がある． Linux では /proc/プロセスID/maps というファイルを cat コマンドなどで見れば良い． macOS (Darwin) では vmmap プロセスID というコマンドを実行すれば良い．

課題4

発展課題：単位取得のためには提出は必須ではないが，提出すれば加点する．

長さ M の整数の列を表現するデータ構造を作成し，列に含まれる整数の和 S を求める処理を N 回繰り返し，データ構造を解放し，S を表示するプログラムを作成しなさい．データ構造として配列を使った場合とリスト（構造体とポインタ）を使った場合の両方で，かつ，N が1の場合と10000の場合の両方で，プログラムの処理時間を測定しなさい．処理時間は次の各々の時間に分けなさい．

データ構造を作成して整数の列で埋める時間
和を求める処理を N 回繰り返す時間
データ構造を解放する時間
M の値を調節することによって，配列の場合とリストの場合の少なくとも片方の総処理時間が数秒から数十秒程度になるようにしなさい．どんな整数の列にするかは自由とする．たとえば，1が最初から最後まで並んでいる列でも良い．処理時間を測定するのは，情報科学類の端末の Mac 環境や Linux 環境でも，情報科学類の Linux サーバ環境でも，全学計算機システムの端末やサーバの Linux 環境でも良い．どの環境で測定したのかを明記すること．
ヒント：上記の環境では，高精度の時刻を取得できるライブラリ関数として，clock_gettime や gettimeofday が使える．詳細については，マニュアルを参照してほしい．

システムプログラミング序論 演習

演習6： 関数ポインタ，エラーとエラー処理

例題1： 多くの分岐先に分岐するプログラム

課題1

例題2： 関数ポインタを用いたプログラム

課題2

例題3： メモリアクセスのエラーを含ませやすいプログラム

課題3

課題4

システムプログラミング序論演習

演習6：関数ポインタ，エラーとエラー処理

例題1：多くの分岐先に分岐するプログラム

例題2：関数ポインタを用いたプログラム

例題3：メモリアクセスのエラーを含ませやすいプログラム