卒業研究で、ビニールハウスの設備制御のためのセンサーと制御対象の無線ネットワーク を構築しようということで、取り組んでいる学生さんの試作品。 ガチャポンに入れたセンサー値を、受信側でモニタリング中。

村田先生の所では、共同研究にてトマト収穫の判定のための画像処理を 試しているそうです。 んで、成果物ということで、お裾分けを頂きました。 トマトは、ダイエットにいいんだよ….とよく食べてますが、 美味しく頂きました….。

でも実験というからには、収穫時期を逃した"熟れきった"サンプルも必要でしょうが、 これは、Bestタイミングなサンプルです。

前回のリストを使った集合演算のように、データを連ねたリストは、 単純リストとか線形リストと呼ばれる。 特徴はデータ数に応じてメモリを確保する点や、途中へのデータの挿入削除が得意な点 があげられる。 一方で、配列は想定最大データ件数で宣言してしまうと、 実際のデータ数が少ない場合、メモリの無駄も発生する。 しかし、想定件数と実データ件数が一致していれば、無駄も必要最小限となる。 リスト構造では、次のデータへのポインタを必要とすることから、 常にポインタ分のメモリは、データにのみ注目すれば無駄となる。

もう１つの欠点がシーケンシャルアクセスとなる。 テープ上に記録された情報を読む場合、後ろのデータを読むには途中データを読み飛ばす 必要があり、データ件数に比例したアクセス時間を要する。 一方配列は、どの場所であれ、一定時間でデータの参照が可能であり、これは ランダムアクセスと呼ばれる。O(1)のアクセス時間。 線形リストは、シーケンシャルアクセスを行うため、データ件数が増えれば N番目 データの参照には、O(N)の時間を要する。

このため、エディタの文字データの管理などに単純リストを用いた場合、 １つ前の行に移動するには、先頭から編集行までの移動で O(N) の時間がかかり、 大量の行数の編集では、使いものにならない。

これらの問題に対応するために、１つ前のデータへのポインタを保存する、 双方向リストが利用される。

struct BDList {
struct BDList* prev ;
int  data ;
struct BDList* next ;
} ;

このデータ構造の特徴を理解してもらうための簡単なプログラムとして、 双方向リストの指定ポインタの前に１件データ挿入を紹介。

void insert( struct BDList* p , int x ) {
struct BDList* n ;
n = (struct BDList*)malloc( sizeof( struct BDList ) ) ;
if ( n != NULL ) {
n->data = x ;
n->prev = p->prev ;
n->next = p ;
p->prev->next = n ;
p->next = n ;
}
}

ファイルの話はほぼ終わったので、リダイレクトとパイプについて説明を行う。

標準入出力とリダイレクト

以下のプログラムは、先週バッファリングの説明のために示した、 入力の小文字を大文字に変換して出力するプログラム。 まずは、このプログラムを保存し、実行プログラム”upper.exe”を 起動し、バッファリングが使われていることを再確認。

#include <stdio.h>

int main() {
   int c ;
   while( (c = getchar()) != EOF ) {
      if ( c >= 'a' && c <= 'z' )
         c = c - 'a' + 'A' ;
      putchar( c ) ;
   }
   return 0 ;
}

• upper.c

標準入力とは、通常キーボードに割り当てられているが、 通常のOSでは、入力をプログラム起動時にファイルに切り替えて実行することができる。

((コマンドプロンプトを開いて、))
((upper.c と同じディレクトリに入る。))
$ upper.exe
This is a pen.
THIS IS A PEN.
^C
$ upper.exe < upper.c
#INCLUDE
INT MAIN(){
:

ファイルに切り替えて実行するには、 “<“マークの後ろにキー入力の代わりのファイルを書けばいい。 この様な機能を”入力リダイレクト”と呼ぶ。

出力リダイレクト

同じように、通常ディスプレイに割り当てられているが、 プログラム起動時に出力を画面でなくファイルに保存するように実行するには、 “>”マークの後ろに保存先のファイル名を書けば良い。 このような機能を”出力リダイレクト”と呼ぶ。

((出力リダイレクト))
$ upper.exe > out.txt
This is a pen.
That is a pencil.
^C
$ type out.txt
THIS IS A PEN.
THAT IS A PENCIL.

((入力リダイレクトと出力リダイレクト))
$ upper.exe < upper.c > out.txt
$ type out.txt
#INCLUDE
:

出力リダイレクトの際に、”>> ファイル名” を付けた場合は、 追記モードで書き込みが行われる。

$ echo "abc" > out.txt
$ type out.txt
abc
$ echo "def" >> out.txt
abc
def

パイプ

入力リダイレクトでは、標準入力をデフォルトのキー入力をファイル入力に 簡単に切り替えることができる。 同様に、出力リダイレクトでは、標準出力の画面を、ファイル出力に 簡単に切り替えることができる。 言い方を変えれば、キー入力や画面出力とファイル入出力を、 同じ概念で操作できる所が大きな特徴。 これと同じように、プログラムの出力と別のプログラムの入力も、 区別なく使うことができたらさらに便利ではないか？

((リダイレクトでabcdeを大文字変換))
$ echo "abcde" > out.txt
$ upper.exe < out.txt
ABCDE
((上記作業を一発で実行))
$ echo "abcde" | upper.exe
ABCDE

この例では、echo プログラムの出力をそのまま upper.exe の標準入力に渡し、 そのupper.exe の標準出力として、ABCDEが画面に表示されている。 プログラム起動時の”|”がパイプで、左側のプログラムの標準出力を 右側のプログラムの標準入力に渡している。

パイプの話の延長として、WebのCGIプログラムではパイプが使われていることや、 フィルタプログラムを組み合わせれば複雑なプログラムを書かなくていいなどを説明する。 また、フィルタプログラムでは、処理中に発生したエラーの警告をprintfで出力すると、 警告メッセージが次のプログラムに送られてしまい、確認ができなくなったり、 警告メッセージのデータを処理できなくなる。このために、標準エラー出力という ものがあることを説明する。

linuxで、Felica(Edy)の読み込みのできるライブラリ libpafe が単純で、使いやすそうだったので、ちょいと遊んでみた。 1秒間隔でポーリングさせ、Edyが認識できる度に"(在室)"と"(不在)"が切り替わるようにしてみた。Edy認識のプログラムを20行ほどと、判断＋表示切替のShell Script を20行ほど、書いてみた。

下の電光掲示板は、随分前にサーバで制御できるようにしてあったので、 かなり簡単にできてます。

// felica.cxx
//
//	EdyのIDを1秒間隔でポーリング。
//	見つけたらIDを表示して停止
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <signal.h>
extern "C" {
#include <libpafe/libpafe.h>
#include <libpafe/pasori_command.h>
#include <libpafe/felica_command.h>
}
// 停止判定
volatile int flag_abort = 0 ;
// ^C による停止の処理
void func_sigterm( int x ) {
flag_abort = 1 ;
}
int main() {
pasori* p ;
// PaSoRiを初期化
if ( (p = pasori_open()) != NULL ) {
felica* f ;
sighandler_t old ;
pasori_init( p ) ;
// pasori_set_timeout( p , 0 ) ; // timeout forever
// イベントハンドラの切り替え
old = signal( SIGTERM , func_sigterm ) ;
while( !flag_abort ) {
// Felicaがあるかチェックする(Edyのみ)
if ( (f = felica_polling( p , FELICA_POLLING_EDY ,
0 , 1 )) != NULL ) {
uint8 idm[ 16 ] ;
// IDmを取得する
felica_get_idm( f , idm ) ;
printf( "%02x:%02x:%02x:%02x:%02x:%02x:%02x:%02x\n" ,
idm[ 0 ] , idm[ 1 ] , idm[ 2 ] , idm[ 3 ] ,
idm[ 4 ] , idm[ 5 ] , idm[ 6 ] , idm[ 7 ] ) ;
// felica_free()があるはずなんだけど...
free( f ) ;
// 強制終了
flag_abort = 1 ;
break ;
}
// 1秒間隔
usleep( 1000000 ) ;
}
// イベントハンドラを戻す
signal( SIGTERM , old ) ;
// PaSoRiを閉じる
pasori_close( p ) ;
}
return 0 ;
}

これを処理する Shell Script。

#!/bin/bash
MY_EDY_ID="11:22:33:44:55:66:77:88"
EDY_ID="/usr/local/bin/edy_id"
EABADGE="/usr/local/bin/eabadge.pl"
STATE="HERE"
while [ "$STATE" != "" ]; do
case $STATE in
HERE ) $EABADGE -f "(在室)" ;;
OUT  ) $EABADGE -f "(不在)" ;;
esac
GET_ID=`$EDY_ID`
while [ "$GET_ID" != "$MY_EDY_ID" ]; do
GET_ID=`$EDY_ID`
done
case $STATE in
HERE ) STATE="OUT" ;;
OUT  ) STATE="HERE" ;;
esac
done

ファイル入出力の課題中であるが、並行して1文字/1行・入出力関数の説明を行う。

1文字入出力関数

1文字単位の入出力関数は、以下のとおり。

int fgetc( fp ) // ファイルから1文字入力
getchar()       // 標準入力から1文字入力
fputc( c , fp ) // ファイルに１文字出力
putchar( c ) // 標準出力に1文字出力

fgetc,getcharは、読み込みデータがこれ以上無い場合には、EOF(#defineで-1)が 帰ってくる。使い方の一例は以下のとおり。

FILE* fp ;
if ( (fp = fopen( "hoge.txt" , "rt" )) != NULL ) {
int c ;
while( (c = fgetc( fp )) != EOF ) {
putchar( c ) ; // ファイルからのデータを標準出力に
}
fclose( fp ) ;
}

fgetc(),getchar() は、読み込んだ1文字データの文字コードを返す。 これ以上読むデータが無い場合は、-1(EOF)を返す。 このため、文字コード(256通り)と"-1"を合わせた257通りが考えられるため、 読み込んだ値を保存する c は、char型でなくint型でなければならない。

入力バッファリング

getchar() の例として、入力の小文字を大文字に変換するプログラムは、 以下のようになる。このプログラムを動かすと、本来であれば１文字入力・変換・出力 の繰り返しであり、キーボードで"abc"と入力すれば、１文字毎に大文字が出力され、 画面には、"aAbBcC"と表示されると思われがちである。

int c ;
while( (c = getchar()) != EOF ) {
if ( c >= 'a' && c <= 'z' )
c = c-'a' + 'A' ;
putchar( c ) ;
}

しかしながら、getchar()などの関数は、バッファリングが行われるため、 特にgetcharでは、行単位のバッファリングが行われる。 プログラムで入力処理が始まると、1行分のデータが溜まるまで、getchar()からは 値が読み取れない。１行のデータが溜まった時点で、その蓄えられたバッファから、 １文字づつ読み取られ処理が繰り返される。

1行入出力関数

1行単位のファイル入出力では、fgets() , fputs() が使われる。 標準出力の文字列出力では、puts()が使われる。

FILE* fp ;
if ( (fp = fopen( "in.txt" , "rt" )) != NULL ) {
char str[ 100 ] ;
while( fgets( str , sizeof( str ) , fp ) != NULL ) {
puts( str ) ;
}
fclose( fp ) ;
}

前回の授業でStack(LIFO)を説明したので、 今日はQueue(FIFO)を説明する。

待ち行列Queue

待ち行列(Queue)は、FIFO(First In First Out)を配列で実装する場合、 一般的には、以下のようになる。 ただしエラー対策は記載していないので、要注意。

int que[ 100 ] ;
int wp = 0 ; // 書き込み用ポインタ
int rp = 0 ; // 読み出し用ポインタ
void put( int x ) {
que[ wp ] = x ;
wp = (wp + 1) % 100 ; // 循環させる
}
int get() {
int ans = que[ rp ] ;
rp = (rp + 1) % 100 ; // 循環させる
return ans ;
}

このような配列の領域を使い切ったら、先頭から再利用するような方法は、 リングバッファなどと呼ばれる。 このような待ち行列は、キー入力バッファや、プロセス待ち行列などに よく利用される。 しかし、このプログラムでも、配列サイズ以上の データは保存できないので、 リストを用いる。

struct List* top = NULL ;
struct List** tail = &top ;
void put( int x ) {
*tail = cons( x , NULL ) ;
tail = &( (*tail)->next ) ;
}
int get() {
int ans = top->data ;
struct List* del = top ;
top = top->next ;
free( del ) ;
return ans ;
}

ただし、このプログラムは、 常に１件以上データがリストに入っている場合は 問題がないが、 get() を実行して、データ件数が０件になると、 tail の指す先が おかしくなるので注意が必要。

また、待ち行列では、先頭ポインタと末尾ポインタの２つが必要であるが、 リスト構造の末尾のNULLを、先頭データを指すようにする循環リストと する場合も多い。 特に、プロセス待ち行列を実装するときのラウンドロビン方式 などでは、 末尾まで処理が及んだ次は先頭に戻って処理を行うため、 循環リストは都合がいい。

集合と2進数

集合を扱うプログラムでもリスト構造はよく利用される。 しかし、対比のためにまずは、2進数を使った集合処理を考える。

// 数学的な集合計算
A = { 1,2,3,5,7 }
B = { 1,2,4,8 }
A∩B = { 1,2 } // 積集合
A∪B = { 1,2,3,4,5,7,8 } // 和集合
A-B = { 3,5,7 } // 差集合

この例のような数値の集合であれば、2進数を使ったテクニックで簡単。

int a = (1<<1) | (1<<2) | (1<<3) | (1<<5) | (1<<7) ;
int b = (1<<1) | (1<<2) | (1<<4) | (1<<8) ;
int a_cap_b = a & b ;
int a_cup_b = a | b ;
int n = 値 ;
// nがaに含まれるか？
if ( a & (1<<n) != 0 )
nがaに含まれる ;

ファイル処理に関する説明が終わったので、 ファイル処理の演習を行う。 演習にあたって、バッファオーバフローの危険性やその対応方法などの説明も行う。

演習とファイル入出力

演習は、ファイルの入出力であることから、あらかじめ作っておいたデータファイルを 読み込み、何らかの加工を加えてファイルに出力とする。 データは、名前+点数5科目、名前+身長体重、名前+生年月日より、 出席番号に応じて課題に取り組む。

ファイル入力+出力の処理の大まかは、以下のとおりになるだろう。

FILE* fp_in ;
FILE* fp_out ;
if ( (fp_in = fopen( "..." , "rt" )) != NULL ) {
if ( (fp_out = fopen( "..." , "wt" )) != NULL ) {
while( fscanf( fp_in , .... ) != ... ) {
fprintf( fp_out , .... ) ;
}
fclose( fp_out ) ;
}
fclose( fp_in ) ;
}

安全な入力

ファイルの説明にあたり、scanf() の %s , %d の入力の仕組みとして、 「基本は空白があれば読み飛ばし、空白を見つけるまでをデータとして格納」 といった説明を、ファイルポインタ(FILE*という意味でなく、ファイル上の読み書き位置の意味)を交えながら解説する。

char  str[ 10 ] ;
scanf( "%s" , str ) ;

安全な入力対策として、上記のような入力は、10文字以上のデータを与えた場合、 危険であることを説明する。 特に、文字配列が局所変数であれば、近辺にある"関数からの戻り番地"も破壊される 可能性がある。さらに配列をはみ出す領域に、悪意のあるプログラム(機械語)を配置し、 関数戻り番地をそのプログラムに合わせることができれば、悪意のあるプログラムを 起動できることを説明する。(一般的にバッファオーバフローと呼ばれる)

このため、バッファオーバフローを起こさないためにも、入力文字制限の 可能な fgets() を使用するなどのテクニックも紹介する。

FILE* fp ; // 何らかのファイル
char buff[ 100 ] ;
while( fgets( buff , sizeof( buff ) , fp ) != NULL ) {
char name[ 100 ] ;
int  data ;
if ( sscanf( buff , "%s%d" , name , &data ) == 2 ) {
// name,dataを使った処理
}
}