[タイトル][SDL][C言語実験室][Kanon専用DNMLビューアKDVXA][BM][ブロック崩し2000][マインスイーパー][ドリラー][ソロモンの鍵アナザー][CDプレイヤJoplay][Depth][Baloon Tripper][SDLバカ一代サポート][掲示板][リンク][日記][自己紹介]

 

C言語実験室

ここではC言語で軽い実験をして、プログラミング技術の向上を目指すページです。日本には様々なC言語の本があるので勉強しやすいかというと、案外そうでもないようです。やはり本を読んでそのとおりにするだけではダメです。疑問に思ったことは何でもしてみなくては。

というわけで、C言語を少しまじめに見てみることにします。

書いてあることに嘘が多分に含まれる場合があります。用心深くお読みください。また、疑問、指摘など大歓迎です。メールか掲示板へお願いします。

第一回 配列って変?(2000/5/9)

実は日記にもちらりと書いたんですが、もう少しきっちり突っ込んでみたいと思います。まず配列って何でしょ?同じデータ型を一括して扱うときに使用する型ですね。しかしいろいろ制限事項があります。

int a[10];

と宣言した場合、a[0]〜a[9]までの10個のint型データを保存できる領域を確保したという意味です(あるいは、もうすでにしてあるという意味)。しかし確保しただけで実際にはどのようなアクセスでも許してしまいます。

a[10]=1;

よくある「やっちゃダメ」とC言語の本に書いてある例ですが、別にこのような記述をしてもコンパイラは怒ったりせず、にこやかにソースを通してくれます。もちろん領域外にデータを書きこむので動作は保証されません。一度試した例にこのようなものがあります。

a[-1]=1;

怖いですね。ちょっと想像できないデータアクセス方法です。しかしシステムによっては例外が出ずに正常終了することもあります(Linux gcc/i386とか(笑))。

さて、上の例についてはポインタを使えばある程度理解できます。すなわち

int a[10];
int *p;
p=&(a[0]);
ここで
a[-1]と*(p-1)は同義

という風に見るとなるほどしっくり来ます。もちろん確保されていない領域へのアクセスとなります。この手のバグはコンパイラどころかデバッガーでも探せなかったりします。通常書きこんではいけない場所へデータを書きこんだりすると一般保護例外とかセグメンテーションフォールトとか出てプログラムは停止しますが、この程度の、たかだか4バイトずれた位置への書き込みくらいでは例外だと認知されないことも多いです。

さて前座はこれくらいにして、配列は他のデータ型と決定的に違う点があります。それはなんでしょう?

リスト1
f(int b[10]){
何らかの処理
}
main(){
 int a[10];
 f(a);
}

さて一見正しく見える関数呼び出しですね。しかし例えば

リスト2
f(int b){
何らかの処理
}
main(){
 int a;
 f(a);
}

と比べてみましょう。分かりますか?リスト2は特に問題ないでしょう?しかし、リスト1の関数fにまるで仮引数用の配列が用意されているかのようです。そして、呼び出し側の配列が関数の仮引数側にコピーされているかのようなイメージですが、まったく、ぜんぜん、ちっとも違います。実はbはint型ポインタで、呼び出し側はのaは&(a[0])と同義です。つまりf内ではbという変数を用いて、main内のaを取り扱っていることになります。

そうです。配列を関数のデータとして渡すことができないんです。

構造体はコピーできますが、配列はコピーできないのも同じ事を意味しています。

int a[10],b[10];
struct A c.d;
c=d;//OK.
a=b;//NG.

つまり配列はポインタと同じと言えます。配列自身に配列の大きさなどの情報はないですし、コピーもできません。a=bの場合、&(a[0])=&(b[0]);と同義ですから、変数aはbと同じデータを共有することになります。そして以前持っていたデータは忘却のかなたへ…。

関数へデータを渡そうにも、データのアドレスを渡すしかありません。逆にポインタも配列といえるかもしれません。

リスト1
f(int *b){
b[0]=1;
}
main(){
 int a[10];
 f(a);
}

というふうに、bはポインタでありながら、b[0]=1と、配列であるかのようにアクセスできます。というわけで配列って少し変、みたいな話でした。intをcharに置き換えて文字列操作を考えると、いい練習になるかも。

第二回 続・配列って変?(2000/5/14)

第一回で嘘を書いてしまったようです。修正しつつポインタと配列の違いをもう少し見てみます。

さて早速間違い個所を挙げてみます。

つまり配列はポインタと同じと言えます。配列自身に配列の大きさなどの情報はないですし、コピーもできません。a=bの場合、&(a[0])=&(b[0]);と同義ですから、変数aはbと同じデータを共有することになります。そして以前持っていたデータは忘却のかなたへ…。

配列の大きさなどの情報はあります。ためしに

int a[10];
printf("%d",sizeof(a));

というプログラムを実行した場合、int型が4バイトならば40と表示されます。つまりあらかじめ確保したメモリサイズはどこかに記憶しているようです。「配列の大きさを得る」ことがどんな風に活用できるか考えてみました。次のような場合、どうでしょうか。

char *command[]={
 "PUT",
 "GET",
 "QUIT",
};
int n_command;

n_command=sizeof(command)/sizeof(command[0]);

こんな感じで、コンパイラが自動的に配列サイズを決めてくれるような状況で活用できそうです。この場合はn_commandに入るのは3ですが、command文字列が増えても自動的にn_commandが調整されます。う〜ん、楽。

次に

int a[10],b[10];
struct A c.d;
c=d;//OK.
a=b;//NG.

というソースですが、コンパイラが許しません。

a=b

の部分でエラーになります。aは結局&(a[0])にすぎず、値を代入することはできません。

さて、次の違いは分かりますか?

char *a="hello";
char b[]="hello";

何が違うのでしょう?両方ともデータ的には同じですが…

答えを言いますと、ポインタの方はコンパイル時に静的な領域に"hello"というデータを確保し、そこへのアドレスが渡されています。配列の方は配列用のデータ領域が確保されていて、この初期化コードが実行されるときになって、配列データへhelloという文字がどこからともなくコピーされます。

プログラム的に考えてみますと…

f(){
char *a="hello";
char b[]="hello";
return(a);←特に問題無し
return(b);←ヤバイ
}

としたとき、もちろんaもbもf内でしか存在できません。また、b[]の中身も関数の終了と伴に保証されないデータとなります。しかしaが指しているデータは消えません。なぜなら静的に確保されているからです。付け加えておきますと、aが指しているデータへのアクセス(書きこみの事)も認められません(認められるCコンパイラもあるようですが)。この"hello"はコード側にあるのでデータとは区別されているのです。

まとめておきますと、

1.配列データを一括してやり取りすることはできない
2.配列データを関数に渡す場合はアドレスを渡すしか方法がない
3.配列データはポインタで扱うしかない

といった所でしょうか?

第三回 メモリ確保(2000/5/23)

char c1[]="abcde"
char *c2="abcde"

の違いは結局、プログラマー側で変数の領域を確保しているか、していないか、でしょう。自分で確保していない場合、読み出し専用です。
さて、データを扱うためには領域を確保しなければなりません。確保の仕方はmalloc関数などを用いて

int* p;
p=(int *)malloc(sizeof(int));

とすることでメモリのどこかに自分が自由に使えるint型領域を設けて、そこへのポインタを得ます。たかがひとつのint型変数に対してmallocを用いてメモリ確保することは珍しいですが構造体のようなまとまったデータ型に対しては(少なくとも私は)頻繁に使用します。

T* p;
p=(T *)malloc(sizeof(T));

mallocは主として配列用領域確保に使用されます。コンパイル時に配列の要素数が決まらない場合など多々ありますのでよく利用します。例えば

int* p;
p=(int *)malloc(sizeof(int)*n);

は、int型領域をn個連続で確保したと言う意味です。すると*p,*(p+1),*(p+2)…は p[0],p[1],p[2]…に対応します。

メモリが足りない場合、NULLポインタが返ってきます。よほどのことがない限りあり得ない事なのですが、きちんとエラー処理しなければなりません。逆に未確保ポインタにNULLを入れておくというテクニックは常用されます。確保した領域は使用後に解放しなければなりません。C以外の言語では自動的に解放してくれる機構をもつものもありますが、Cでは解放を明示しなければなりません。自ら確保した領域をpが指しているとして、これを解放する場合、次のように書きます。

free(p);

このときpが指す領域の大きさを指定する必要はありません。たぶんmallocがどこかに覚えさせているのでしょう。確保していない領域をfreeしようとすると間違いなく例外をだしてプログラムは終了するはずです。
malloc-freeの例として、C言語の本に例としてよく載っている2重配列(例えばm行n列の行列)を2重ポインタを利用して作ってみます。
型は何でもいいのでTとすると

T** Talloc(int m,int n){
 int i;
 T **p ,**q;
 p=(T**)malloc(sizeof(T*)*m);
 if(p==NULL){
  エラーメッセージ出力など;
  return(NULL);
 };
(**)
 for(i=0,q=p;i<m;++i,++q){
  *q=(T *)malloc(sizeof(T)*n);
  if(*q==NULL){
(*)  それまで確保したメモリの解放&エラー出力;
   return(NULL);
  }
 }
 return(p);
}

ここで面倒なのは(*)の部分です。中途半端にメモリを確保して途中でメモリがなくなった事を想定してみます(まあ、そんなことはほとんどないのですが)。どこまで確保したかをiとqが保持しているので

for(--i,--q;i>=0;--i,--q)free(*q);
free(p);

みたいな感じでしょうか?しかしわざわざ確保失敗時に解放処理を書くのは、もったいない感じがします。どうせ確保したものは解放しなくてはならないので解放用の関数を書いてしまいましょう。このときに中途半端に確保したものでも解放できるように書きます。

void Tfree(T** p,int m){
 int i;
 T** q;
 if(p==NULL)return;
 for(i=0,q=p;i<m;++i,++q)if(*q!=NULL)free(*q);
 free(p);
}

そして確保時(**)に、ポインタへNULLを入れておきます。

memset(p,0,sizeof(T*)*m);

エラー処理部(*)は

Tfree(p,m);

でOK。
ただし、これが使えるのはNULLの値が0であるときです。NULLが0でない場合は確保時にいちいちポインタへNULLを入れてやらねばなりません。

第四回 無駄(2000/5/28)

C言語FAQに大抵の事例が載っているので、このドキュメント自体無駄のような気がしないでもないです。さて、無駄といえば前回のプログラムには冗長な部分が含まれています。後から見れば、どう言う心理状態が働いたのか理解に苦しみます。そんな事が多いのは自分だけでしょうか…

問題の部分は以下の通り。

T** Talloc(int m,int n){
 int i;
 T **p ,**q;
 p=(T**)malloc(sizeof(T*)*m);
 if(p==NULL){
  エラーメッセージ出力など;
  return(NULL);
 };
(**)
 for(i=0,q=p;i<m;++i,++q){
  *q=(T *)malloc(sizeof(T)*n);
  if(*q==NULL){

とありますが、なぜqとiの二つの変数を使っているのかさっぱり理解できません。なんでこんなコードを書いたんでしょうか。どちらかひとつにまとめるべきです。つまりfor文の所を

 for(i=0;i<m;++i){
  *(p+i)=(T *)malloc(sizeof(T)*n);
  if(*(p+i)==NULL){

のように書きかえるべきです。そうすれば無駄なqという変数を導入せずに済みます。もちろん*(p+i)をp[i]と書いても同じ意味です。iを使わない場合は

 for(q=p;q<p+m;++q){
  *q=(T *)malloc(sizeof(T)*n);
  if(*q==NULL){

です。 変数は増えてくると管理が大変なので極力減らすように努力しなければなりません。が、なかなか難しいんですよね。

まだまだダイエットできます。恥ずかしながらfree関数は引数にNULLを与えたときに「何もしない」という動作が保証されていることを知らなかったんですね〜。というわけで、前回のプログラムの

void Tfree(T** p,int m){
 int i;
 T** q;
 if(p==NULL)return;
 for(i=0,q=p;i<m;++i,++q)if(*q!=NULL)free(*q);
 free(p);
}

のfor文中のif文は無駄です。ついでに、ここもiとqを両方無駄に使おうとしていますね。直すと

 for(i=0;i<m;++i)free(p[i]);

です。ちなみにfreeしなくてもプロセスが終了するときにmallocで確保したメモリなどは自動的に解放されるようです。しかしmallocとfreeはペアで使ってきっちりメモリ管理すべきです。自動解放はプロセスが終了しなければ有効でないわけですから。

第五回 続ポインタと配列の違い(6/2)

第二回でなにやら怪しげな説明をしていますが、アセンブラコードを吐かすことによって厳密に見てみることにします。今回のトピックを読むためには、アセンブラの知識が必要になるため若干敷居が高いかもしれません。おまけに筆者はアセンブラコードを見るのは数年ぶりなので間違えているかもしれません。

リスト1(test.c)

main(){
 char a[]="abcde";
 char *b="fghij";
 a[1]='a';
 b[1]='a';
}

をコンパイルするときに

gcc -S -O0 test.c

とオプションを付けてコンパイルするとtest.sというファイルが出来ます。これがコンパイルだけ(正確にはプリプロセスとコンパイルだけ)した場合の出力コードです。-O0は最適化レベルを表していて、0の場合、最適化しません。出力コードはアセンブラで書かれています。説明のために付け加えた行には#を入れてあります。私はMASMやTASMなどをMSDOS上で使っていたため、オペランドの順番が逆転している下のリストを見て少しビビりました。例えばMSDOSでは

mov al,2

となるところが、Unixでは

movb $2,%al

と、なります。
意味はレジスタalに2を代入するということです。
また、間接アドレッシングの記号も違っていて、

movl %edx,-16(%ebp)

mov [ebp-16],edx

と同じ意味です。

では、アセンブラコードを見ていきましょう。以下はi386のgcc/cygwinでコンパイルしたものの出力結果です。


.file "test.c"
gcc2_compiled.:
___gnu_compiled_c:
.def ___main; .scl 2; .type 32; .endef
.text
LC0:
.ascii "abcde\0"
LC1:
.ascii "fghij\0"
.align 4
.globl _main
.def _main; .scl 2; .type 32; .endef
_main:
 pushl %ebp
 movl %esp,%ebp
 subl $32,%esp
 call ___main

#(1)
#char a[]="abcde";
#(&a[0]=%ebp-16.)

 leal -16(%ebp),%eax
 movl LC0,%edx
 movl %edx,-16(%ebp)
 movw LC0+4,%ax
 movw %ax,-12(%ebp)

#(2)
#char *b="fghij";
#(&b=%ebp-20.)

 movl $LC1,-20(%ebp)

#(3)
#a[1]='a';

 movb $97,-15(%ebp)

#(4)
#b[1]='a'

  movl -20(%ebp),%eax
 incl %eax
 movb $97,(%eax)

L1:
 movl %ebp,%esp
 popl %ebp
ret

基本的にローカル変数はスタックに割り当てられます。関数内で使う変数はebpを介してアクセスできます(というか、せざるを得ません)。配列の場合、要素分のエリアがスタックに確保されます。また、ポインタの場合、4バイト確保されています。ローカル変数用スタック領域は今のところ次のようになっています。

■スタックの様子(その1)
-11 ?
-12 ?
-13 ?
-14 ?
-15 ?
-16 ?
-20 ?

(1)以降を見ていきます。ここからがC言語と対応しています。

(1)いきなり凄まじいことをやっているのが分かります。つまりa[]へ"abcde"をコピーしているのですが、出来る限り32bit幅で一回一回コピーしようとしています。今回は6バイト("abcde"+'\0')なので4+2バイトコピーしています。文字列を長くしてみるとその挙動がよく分かります。

 leal -16(%ebp),%eax
 movl LC0,%edx
 movl %edx,-16(%ebp)
 movw LC0+4,%ax
 movw %ax,-12(%ebp)

詳しく見ます。一行目は無意味なので飛ばします。二行目では、"abcde"文字列があるアドレスから32ビット分(四文字分)、edxへコピーしています。三行目ではa[0]へedxをコピーしています。これで"abcd"がコピーされたことになります。スタックは次のようになります。

■スタックの様子(その2)
-11 ?
-12 ?
-13 d
-14 c
-15 b
-16 a
-20 ?

続く行で16ビット分(二文字分)を"abcde"の"e"の位置からコピーしてaxレジスタへ代入。つまり'e'と'\0'がaxに入っています。これをa[4]の位置へコピーしているのが最後の行です。これで"abcde"+'\0'の6バイトコピーが完了しました。

■スタックの様子(その3)
-11 \0
-12 e
-13 d
-14 c
-15 b
-16 a
-20 ?

というわけで初期化の

 char a[]="abcde";

には、これだけの意味が込められています。

(2)それとは対照的にポインタの初期化がどうなっているのかを見てみると…

 movl $LC1,-20(%ebp)

たったこれだけです。「ポインタ変数は指すだけ」というのがはっきり表れています。ebp-20に、ポインタ変数が4バイトで存在します。i386ではポインタの大きさは32ビットなのです。そこへ"fghij"のあるアドレスをコピーしています。

■スタックの様子(その4)
-11 \0
-12 e
-13 d
-14 c
-15 b
-16 a
-20 $LC1(4バイト)

(3)実際に配列へアクセスする場合、

 movb $97,-15(%ebp)

となっていて、直接スタックへアクセスしています。a[0]の位置はebp-16なのでa[1]はebp-15です。もちろん、$97は'a'の事です。

(4)ポインタで同様のアクセスをする場合、

  movl -20(%ebp),%eax
 incl %eax
 movb $97,(%eax)

まず一度汎用レジスタへアドレスを読み込みます。必要な操作をした後、間接アドレッシングにてアクセスします。データがどこにあるのかポインタのみぞ知る、という感じです。一行目でポインタが指すアドレスをeaxに入れます。指したいデータはb[1]なので、eaxの内容を1増やします。例えばb[4]の場合は

 addl $4,%eax

みたいな感じになるでしょう。そして最後の行で代入が実行されます。 ポインタは汎用レジスタで取り扱われているみたいです。従って汎用レジスタの幅によってポインタの大きさが変わります。DEC/Alphaなどは64ビット長のポインタを持っていますが、汎用レジスタが64ビット幅なんでしょう。

アセンブラコードを見るのは中々面白いですね。今回はポインタと配列の違いでしたが、他にも最適化の振る舞いや、構造体へのポインタの振る舞いなど、興味が尽きません。いずれそれらについても触れてみようと思います。

第六回 文字コードその1(6/15)

いままではCそのものを見ていましたが、今回はCを離れて少し実装上の問題を見てみることにします。さて、日本にいる以上、日本語問題が付きまといます。例えばC言語で文字型とされているchar型は8ビット幅であるため、漢字のように大量に文字がある系ではcharでは表現しきれません。そこで漢字の様々な表現法が今現在あります。

1.JIS
2.EUC
3.Shift JIS
4.Unicode

これらはすべて漢字を表現できる文字規格ですが、それぞれ形式が違っています。Windows系では主にShiftJISが使用されていますが、Unix系ではEUCです。また、JavaはUnicodeを文字として扱っています。Unicodeは多国語サポート用の文字コードで、Unicodeの中でもいろいろな形式が存在します。

自力でフォントなどを作成あるいは参照するときには漢字コードを意識しなければなりません。例えばbdfファイルはテキストで書かれたフォントで、以下のようにフォントが記述されています。jiskan24.bdfというファイルの一部です。

STARTCHAR 5b65
ENCODING 23397
SWIDTH 144 0
DWIDTH 24 0
BBX 24 24 0 -2
BITMAP
0E100C
0C1FFE
0C180C
0C180C
0D980C
FFDFFC
0C180C
0C180C
0C180C
1E1FFC
以下続く

これは文字コード5b65の漢字イメージです。BITMAP以下ビットイメージになっていて1ライン24ドットであることがわかります(3バイト=24ビット)。固定24ドットフォントなのでBITMAP以下24ライン続きます。さて問題は5b65というコードナンバーですが、これは先のコードのどれに当たるのでしょう?答えはJISコードになります。従ってWindowsなりUnixなり、文字コードをJISに変換してからこのグラフィックを参照しなければなりません。例えばWindowsで

unsigned char a[]="こんにちは";

と書いた場合、たいていShiftJISでaに格納されています。ShiftJISはchar型の中にうまく潜り込むことが出来るのでよく使われています。まず、*a,*(a+1)の部分('こ')のShiftJISコードは

code= ((*a)<<8) + (*(a+1));

でゲットできます。これから漢字イメージを検索する場合、JISへ変換します。

//shift jis -> jis
void sjis2jis( unsigned char *c1, unsigned char *c2)
{
 if( *c2 < 0x9f )
 {
  if( *c1 < 0xa0 )
  {
   *c1 -= 0x81;
   *c1 *= 2;
   *c1 += 0x21;
  }
  else
  {
   *c1 -= 0xe0;
   *c1 *= 2;
   *c1 += 0x5f;
  }
  if( *c2 > 0x7f )
  -- *c2;
  *c2 -= 0x1f;
 }

 else
 {
  if( *c1 < 0xa0 )
  {
   *c1 -= 0x81;
   *c1 *= 2;
   *c1 += 0x22;
  }
  else
  {
   *c1 -= 0xe0;
   *c1 *= 2;
   *c1 += 0x60;
  }
  *c2 -= 0x7e;
 }
}

これはどこかで見つけてきたものですが、思ったより複雑です。複雑ですが計算式で変換できることが分かると思います。使い方はc1に上位一バイト、c2に下位一バイトを渡すと勝手に書き換えてJISコードにしてくれるという関数です。

第七回 文字コードその2(7/2)

TrueTypeフォントをご存知でしょうか?ウインドウズなどでおなじみの、大きさを変えてもドットが目立たないタイプのフォントです。これは文字の形をベクトルで保存しているためです。さて、このtruetypeフォントをプログラム上で扱いたい場合、このデータ形式を取り扱うプログラムを書くか、あるいはライブラリを利用しなければなりません。前回のような単純なビットマップ形式であれば自分で書くのは楽ですが、TrueTypeフォントの場合、結構面倒で、それよりもライブラリを使う方が楽です。

TrueTypeフォントをレンダリングする場合、freetypeという文字通り自由に使えるライブラリがあります。しかしこのfreetypeは漢字付きASCII文字をレンダリングすることができません。代わりにUnicodeによる2バイト文字などをサポートしています。従って、freetypeで文字をレンダリングする場合はShiftJisからUnicodeへ変換する必要があります。

ShiftJisからJisへ変換する場合は一定の規則があったので前回のような演算による変換が可能でしたが、UnicodeとShiftJisの間には相関関係が無いので、完全なテーブル変換となります。変換テーブルは以下で手に入ります。

ftp://ftp.unicode.org/Public/MAPPINGS/EASTASIA/JIS/

変換テーブルは

0x829F 0x3041 # HIRAGANA LETTER SMALL A
0x82A0 0x3042 # HIRAGANA LETTER A
0x82A1 0x3043 # HIRAGANA LETTER SMALL I
0x82A2 0x3044 # HIRAGANA LETTER I
0x82A3 0x3045 # HIRAGANA LETTER SMALL U
0x82A4 0x3046 # HIRAGANA LETTER U
0x82A5 0x3047 # HIRAGANA LETTER SMALL E

というフォーマットになっていて左がShiftJIS値、右がUnicode値です。

ShiftJIS文字はascii文字の中の潜り込んでいます。つまり、8ビット文字と16ビット文字が混在しているため、Unicodeへ変換する際には、まず、8ビット文字をすべて16ビット文字に変えます。short intが16ビットだとして、

unsigned char a[10]="abcいろは";

内訳:

a[0]='a';
a[1]='b';
a[2]='c';
a[3]='い'の上位バイト
a[4]='い'の下位バイト
a[5]='ろ'の上位バイト
a[6]='ろ'の下位バイト
a[7]='は'の上位バイト
a[8]='は'の下位バイト
a[9]=0

と対応するのは

unsigned short int b[7];
b[0]='a';
b[1]='b';
b[2]='c';
b[3]='い';
b[4]='ろ';
b[5]='は';
b[6]=0;

と、なります。asciiかShiftJisかの判定は文字が7bit以内かどうかで判断します。例としてはpがasciiあるいはShiftJIS文字を指しているとして

unisgned char *p;
unsiened char high,low;
unsigned short int index;
if( *p > 127 ){
 high=*p;
 low=*p+1;
 p+=2;
}else{
 high=0;
 low=*p;
 p++;
}
index= (high<<8) +low;

みたいな関数を作って、asciiを16ビット文字にしておき、テーブルからUnicodeへ変換すればOKです。 実用例としてSDL_ttfライブラリのサンプルプログラムであるshowfontのShiftJIS日本語対応バージョンを示しておきます。

tttest.tgz(4kb)

第八回 CをC++に近づけてみる(7/15)

筆者はほとんどオブジェクト指向型言語に触ったことがありません。C++にしてもJavaにしてもDelphiにしても、ほんの少し使った程度です。主にゲームプログラムとその付近しか興味がなかったのか、昔のスタイルであるC言語(+アセンブラ)をそのまま続けています。オブジェクト指向型言語については、ようやく勉強に本腰を入れ始めたところです。が、オブジェクト指向についてちょっと思ったことを書いてみます。

オブジェクト指向は、大昔、構造化プログラミングが提唱されだしたのと同じような、センセーショナルな考え方です。C言語でいえば、「変数は、関数が取り扱うデータ群」と考えるのではなく、「データ(変数)に付随する関数群」というふうに考えるので、非常に新鮮味を覚えました。こうすることでいくら関数が増えても「データの下にある」ため、階層管理できます。

まあ、オブジェクト指向は何も言語に付随したアイテムではなく、ひとつの哲学に過ぎないのでC言語であっても(C++でなくても)オブジェクト指向的プログラミングは可能であると考えます。

継承をとりあえず考えないことにすると、オブジェクトとは

データ+データ処理部

このように、くっつけたようなイメージで良いと思います。Javaで言えばプロパティ+メソッド、C++で言えばメンバ変数+メンバ関数です。これが雛型となり、新たな型として振舞うわけです。C++はC言語にオブジェクト指向的機能を付随してありますが、Cで自前でその処理をやってしまえばC++に近い記述が可能というわけです。

クラス=(構造体+構造体を取り扱う関数群)

と、考えると…

class A{
private:
int a;
public:
int b(int);
}

typedef struct{
int a;
}A;

int b(A*,int);

と、なるでしょう。メンバ関数と見たてているbは構造体へのポインタを渡しています。実際に関数を記述するところはthisで受けます。これはC++が実際に行うことを忠実に書いているだけで、C++では言語仕様上見えないようになっています。C++で突然thisという変数が(宣言されもせず)使われているのを見て驚かれた人は、この仕組みを知ってしまえば理解できるはずです。これがわかればスタティックメンバ関数やフレンド関数に、なぜthisが無いのか、も、わかるはずです。

メンバの隠蔽や関数名のネーミングなども自前でやらなければなりません。ネーミングに関しては、私の場合、構造体名のあとに関数名をくっつけたような格好にすることが多いです。例えば

class stack{
...
public:
void push(int);
...
}

例:
stack s;
s.push(5);

みたいな場合 、

typedef struct{
...
}stack;
stackpush(stack*,int);

例:
stack s;
stackpush(&s,5);

と、なります。

まあ、こんなことせずにC++を使うのが正解なんでしょうね。

第九回 リカーシブコールについて(7/27)

C言語の本に必ず説明が出てくる再帰関数呼び出しは一体何のためにあるのでしょうか。簡単に使い方から見ていくことにします。
例題として頻繁に挙げられる、nの階乗計算(n*(n-1)*…*2*1)をみてみます。

int kaijo(int n){
if(n==1)return 1;
return(n*kaijo(n-1));
}

kaijo(5);

と関数を呼び出したら
まずkaijo(5)内でn!=1と判断され、5*kaijo(4)を返そうとします。しかしkaijo(4)が関数呼び出しなので、kaijo(4)を実行します。同じようにkaijo(4)内でn!=1と判断され、4*kaijo(3)を返そうとしますが…(以下略)。
最終的にn==1のときに初めて関数呼び出しを行わずに関数が終了します。これが再帰の終端です。このあと、呼ばれた関数が次々返っていきます。

さて、動きがわかったところで、実際にはどのように使うのか考えてみます。だいたい、階乗程度ならfor文などで記述できます。再帰関数は、数学的帰納法で考えられる問題に対してはすべて適用できそうです。ある問題に対して、同じプロセスを繰り返し用いて解くことが可能な場合を挙げてみます。

拙作のマインスイーパーからソースを切り出して見ます。これはマインスイーパーのパネルをめくる処理です。あるパネルをめくって、爆弾や爆弾周囲であれば即刻この関数は終了です。さて、そうでなかったら、周りのパネルも調べていきます。パネルがもし爆弾周囲でなかったら(爆弾である可能性は無い。なぜなら爆弾周囲である状態からこの関数は呼ばれないからである)、やはりその周りのパネルも調べます。すでにパネルが開かれている場合はそこで関数呼び出しは打ち切りです。なぜならすでに開いていると言うことは、そのパネルは同様の方法ですでに処理済ということだからです。このようにして、すでにパネルが開かれているか、あるいは爆弾周囲と判断されるまでこの処理を続けます。ここで、「パネルがすでに開かれている、あるいは爆弾周囲」が再帰関数の終端条件にあたります。

/* めくる座標を引数にとるパネルめくり再帰関数 */
void reveal(int x,int y){

Cstage *p;

/* 着目しているパネルをpで指す */
p=&(stage[x][y]);

/* すでに開かれている?(終端条件1) */
if(p->isOpen)return;

/* 開いたことにする */
p->isOpen=1;

/* パネル残り数を減らす */
real_left--;

/* 最後のパネルを引いた! */
if(real_left==0){
game_state=GAME_CLEAR;
total_thinking=gametime.clock;
}

/* パネルの中が爆弾であった */
if(p->bomb>=MSSTG_BOMB){
openAll();
game_state=GAME_OVER;
}

/* パネルの中が爆弾周囲(あるいは爆弾)であった(終端条件2) */
if(p->bomb!=0)return;

/*
 以上のどれにも当てはまらない場合周囲のパネルを同じ関数を使って開く。パネルの端まできたら、めくらないでおく。
 ここでは隣接する4方向しか開こうとしていないがマインスイーパーの場合、本来は8方向に開くべき。
*/
if(x>1)reveal(x-1,y);
if(x<stage_size_x)reveal(x+1,y);
if(y>1)reveal(x,y-1);
if(y<stage_size_y)reveal(x,y+1);

/* パネルをめくり終えた */

}

リカーシブコールで気をつけておきたいのは、変数領域の確保です。関数内で宣言される変数はstatic指定されない限りスタックに生成されるので、たとえば

int f(){
char a[10000];

}

のような再帰関数を作ると、一度呼ばれるたびに10000バイトのスタック領域を食いつぶします。再帰関数を一度呼ぶと、一気に何度も呼ばれる可能性があるので、どれだけスタックを消費するかわかりません。

第十回 整数化小数、その1(8/6)

浮動小数点計算は整数計算に比べて遅いんです。昔は整数しか取り扱えなかったCPUもあったくらいで、つまり小数計算は難しいのです。そこで、昔からある手法として小数を整数化するというのがあります。これを用いると、小数を擬似的に扱うため精度を犠牲にしますが、高速な計算ができます。今回はそれを説明したいと思います。しかし、その前にいろいろ予備知識が必要だろうと思いますので、冗長ながら、基礎の基礎から説明します。

【2進数】

一般的にn進数と呼ばれる数値は、数字の各桁が0〜n-1までで構成されます。 そして各桁はnのべき乗で表され、このとき、nを基数と言います。われわれが普段使用している10進数を見てみましょう。たとえば、12345という数字は次のように分解できます。

12345=1*10^4+2*10^3+3*10^2+4*10^1+5*10^0

ここで10^4は10の4乗を表しています。これが10進数です。各桁は0〜9によって構成されています。この規則に従って2進数を考えてみましょう。2進数の場合、各桁は0〜1、つまり、0と1だけで表します。カッコの中を基数として、例えば123という数字は

123(10)=1*2^6+1*2^5+1*2^4+1*2^3+0*2^2+1*2^1+1*2^0=111011(2)

と、なります。

n進数の足し算は以下のように行います。例えば
123(10)+567(10)
というのはまず右から数えて一桁目同士を足します。すると、3+7で、10となりますが、10進数の世界では0から9しか存在しないので、10から10進数の10を引いた0を一桁目にします。そして、演算が一桁に入りきらなかったため、桁上がりを1とします。
次に二桁目の計算に入ります。2+6=8で、これに桁上がり分を加えて9、同様に3桁目は1+5=6で、結局この演算の答えは690となります。

同様に2進数の足し算をしてみます。
1010(2)+(1111)(2)
10進数では10(10)+15(10)=25(10)です。2進数ではどうなるでしょう。10進数のときと同じように考えてみます。
まず一桁目は1+0=1。二桁目は1+1=2、しかし2進数の世界では2以上は存在できないので、桁上がり1、2桁目は0。3桁目は1+0=1、2桁目からのけた上がりを加えて2。先ほどと同様に3桁目は0で、桁上がり1。4桁目は1+1=2、桁上がりを加えて3。従って、4桁目は1の桁上がり1。5桁目は演算すべき数値はないので、桁上がりがそのまま現れます。結果この演算の答えは11001(2)であり、10進数に直すと25(10)となります。

【演算限界】

さて、なぜいきなり2進数の話が始まったのでしょうか。それは、コンピュータが2進数しか扱えないからです。例えばC言語のunsigned char型の大きさは1バイトである、と参考書等に書いてあるでしょう? 1バイトは8ビットのことですが、このビットというのは2進数のひとつの桁を表しています。unsigned charはつまり、8桁の2進数です。他の型についても同様です。現時点ではshort intは16ビット、intは32ビット、long intは64ビット(あるいは32ビット)です。

unsigned char型は8ビットなので、表現できる数は2^8種類です。これを0から順に整数を充てたら255まで表現できることになります。では256以降の整数はどうなるのでしょう。

例えば8桁2進数同士の演算、11111111(2)+00000001(2) は1,00000000(2)となります。つまり桁上がりして9桁になるわけですが、8桁までしか表現力の無いC言語のunsigned charは桁上がりを無視します。つまり11111111(2)+00000001(2)=00000000(2)なのです。10進数で言うと、255+1=0というわけです。 桁上がりを無視するので、演算結果は256に到達することなく必ず0〜255の間になります。 unsigned charは一桁の256進数と言えますね。

【負の数、2の補数】

数学の世界にはマイナス記号があるため、負の数の表現が簡単です。数字の前に”−”を付けるだけですからね。コンピュータの世界では、”−”記号なんて便利なものは存在しません。では、例えば負の数が必要になったらどうするのでしょうか。

00000000(2)-00000001(2)は幾らでしょう? コンピュータ内では簡単に答えが出ます。足し算の逆が引き算ですから、A-B=Cすなわち、C+B=Aと式を変形します。ここでは
C+00000001(2)=00000000(2)です。この足し算は上で出てきていますよね。つまりCは11111111(2)です。もともとの演算は0(10)-1(10)と同じなので、これは-1です。しかし、255でもあるのがわかります。不思議ですね。

”−”記号がない以上、数字だけで正か負かを判断しますが、その判断は使う人、つまり”あなた” に任されています。だから11111111(2)を-1と読むか255と読むかはあなた次第なワケです。

さて、11111111(2)を−1と読む場合ですが、これは2の補数表現と呼ばれる方法です。一般的にコンピュータ上で用いられています。

マイナスにしたい数字を挙げて、これを2の補数でマイナスにしてみましょう。
00000001(2)
これは1です。これを負にすると-1です。では、その手順を踏んでみます。
1.まず、各ビットを反転します。反転とは、0なら1に、1なら0にする、という意味です。従って、ここでは
11111110(2)と成ります。これを1の補数と言います。
2.次に1を足します。すると
11111111(2)
となり、2の補数表現による-1の出来あがりです。

2の補数の特徴は
A. 符号付、符号無し演算を混ぜることが出来る
B. 2の補数による負の数は必ず最上位ビットが1になる
です。
A.は例えば255-1をしてみれば分かります。まず、2の補数を使わない場合、
11111111(2)-00000001(2)=11111110(2)
-1に2の補数を使う場合、演算としては255+(-1)という事になります。8ビットであれば
11111111(2)+11111111(2)=11111110(2)
となり、まったく同じ答えになります。
B.は最上位ビット、つまり左から数えて一桁目が必ず1に成るということです。つまりこれをマイナス符号と見ても差し支えない、ということです。符号付というのは最上位ビットを数字表現ではなく、プラスかマイナスかの符号と見たてるという意味です。

C言語でも同様に符号付整数は2の補数表現で表されます。つまり型の前にunsigned と付けないか、あるいはsingedと明示すれば、2の補数として扱われます。

第十一回 整数化小数、その2(8/10)

2進数とコンピュータの演算は表裏一体です。前回書いてあることは、実際にコードを書いて確かめてみてください。さて、今回は2進数における、特殊な演算の説明をします。実は前回説明した足し算などはすべてこの”特殊な演算”から成っています。

【論理演算】

ビット単位で演算をします。C言語では以下の4種類が使えます。カッコの中は演算子です。

■論理和、or(|)…「AとBの論理和を取る」とは、AとBの同じ位のビットを比べて、少なくとも片方が1であれば、その位のビットを1とし、そうでなければ0とする、という意味です。8ビット同士の論理和を挙げて見ます。

10101010 | 11110000 = 11111010

演算の結果、着目している位のビットが1になることを、「ビットが立つ」と言います(私だけが言ってるのかもしれません。ローカル用語なら容赦してください)。論理和はビットを立てたいときに使用します。例えば、ロールプレイングゲームで、主人公達の状態(毒を受けている、石化している、麻痺している、気絶している、などなど)を表すStateという変数があるとします。各ビットでON=1かOFF=0かを表すことができるので、例えば状態に毒と石化を加えたい場合、

#define 毒 1
#define 麻痺 2
#define 石化 4
#define 気絶 8
unsigned char State=0;



/* 毒と石化を受けさせる */

State |= 毒;
State |= 石化;

この場合、変数Stateは、右から数えて1ビット目が毒、3ビット目が石化を表しています。ここでは例としてあげていますが、このような用途には通常、C言語ではビットフィールドという、構造体に付属してくる機能を使うことで実現します。

■論理積、and(&)…「AとBの論理積を取る」とは、AとBの同じ位のビットを比べて、少なくとも片方が0であれば、その位のビットを0とし、そうでなければ1とする、という意味です。論理和も同様に例を挙げてみましょう。

10101010 & 11110000 = 10100000

ある領域を必ず0にしたいとき論理積を取ります。通常、マスクを取るなどと言います。使用例を挙げてみましょう。そちらのほうが説明するよりも分かりやすいでしょう。

先ほどの例で、状態のチェックをするときには次のようにします。

if(State & 毒){

}

こうすることで、毒の場所以外のビットが0にマスクされ、毒ビット(かなり嫌な表現ですね…)だけ0か1かの判定が出来るというわけです。

■排他的論理和、xor,eor(^)…「AとBの排他的論理和を取る」とは、AとBの同じ位のビットを比べて、同じビット値であれば0、そうでなければ1、となります。表にすると

Bit A Bit B 結果
0 0 0
0 1 1
1 0 1
1 1 0

このようになります。用途に少し困りそうなビット演算ですが、例を挙げて見ます。

同じ値同士をxorすると必ず0になりますので、アセンブラではレジスタに0を代入する代わりとして使われていました。ひょっとするとまだ使われているかもしれませんが。

xor al,al

その他の例としては…、ある値に排他的論理和を2度施すと、元の値に戻ります。これを利用して簡易的な暗号をかけることが出来ます。例えば…

データを10101111、暗号鍵を11110000としましょうか。まず暗号をかけてみます。

10101111 xor 11110000 = 01011111

暗号化されたデータの出来あがりです。さて、早速ですが、暗号を外します。

01011111 xor 11110000 = 10101111

この計算は簡単なので、実際にしてみてくださいね。市販のゲーム絵データの隠蔽などにも使用されています。

■否定、not(!)…「Aの否定を取る」とは、Aのビットが0であれば1、1であれば0にする」という意味です。前回書いた「ビットを反転する」のとは全く同じ意味です。例を出すまでもありませんが、一応示します。

not 10101111 = 01010000

論理否定はよくC言語で使われているのでおなじみでしょう。
if(!She->isRunning){

}
isRunningメンバは1か0を取るとします。1は走っている、0は走っていない、と読むとき、
「もしも彼女が走っていなければ…」
と読めそうな気がしませんか。

if文は条件が真の時だけ実行する制御文ですが、もし彼女が走っていなければ、メンバisRunningの否定を取ったときに必ず0以外(真)になり、if文以下が実行されます。

ちなみにすべてのビットが1の数字とxorを取ることで否定と同じ演算が可能です。

10101111 xor 11111111 = 01010000

第十二回 整数化小数、その3(8/23)

【シフト演算】

アセンブラと違ってビットに対する演算の種類は少ないのです。C言語では、もうこのシフト演算しか残っていません。シフトとはビットイメージをずらすことに相当します。例えば右へ1ビットシフトするとは

10101111 → 01010111

となります。この例では8ビット幅で最上位ビットには0が新しく加えられています。シフトした場合、かならず0が挿入されます。演算の意味としては数値を半分にすることに相当します。従って右へnビットシフトすると2のn乗で割ることになります。同様に左へ1ビットシフトする場合、その値は二倍になりますが、8ビット整数においては上の例だと桁あふれを起こします。

10101111 → 01011110

なお、右へシフトするとどうして2のn乗で割ることになるのか、分かりにくい場合は10進数で考えてみましょう。例えば

12345(10)

を右へ1つシフトすると

1234(10)

となりますね。余りを考えなければ、10で割ったことになります。つまりシフトはn進数のnで割ることに相当します。右へ1つだけシフトすると…

123450(10)

となり、10倍されています。

C言語では左シフト"<<"や右シフト">>"という記号を使います。例えば

a<<=1;
a=b>>c;

などのように使用します。変数には符号付と符号無しがありますが、符号なしの変数を使うのが無難です。処理系によっては右シフトの際、符号付変数であれば最上位ビットに1を補完していく可能性があるからです。

10101111 を右へ1ビットシフト → 11010111

この振る舞いはC言語では特に規定されていなかったと思いますので、注意してください。とりあえず、シフト演算をする時には符号なし変数を使ってください。

【整数化小数】

さて、見てきたようにシフト演算は乗除に関係した演算であると言えますが、普通に掛け算や割り算をするよりも高速に演算を行うことが可能です。これを利用して小数を整数で取り扱ってみます。まずは簡単に10進数から見ていきます。

123.45

これは普通の小数です。変数へ代入するならdoubleやfloat型変数が必要です。が、これを左へ2つシフトすると(10の2乗を掛けると)

12345

となり、整数になります。整数であればdoubleなどを使う必要がありませんよね。このように始めに取り扱う数字が、あらかじめ100倍されていると考えます。この数字は123.45を表していますが、既に10の2乗分だけ下駄をはいているのです。現実の値はこれに2つだけ右シフトしてやる(10の2乗で割る)と123.45が得られます。このときの整数で表している小数の精度は0.01(10の2乗分の1)です。

さて、コンピュータの思考に合わせてみましょう。以下ではintが32ビットであると仮定します。まず32ビット型整数を宣言します。

unsigned int x;

この変数はあらかじめ左へ16ビットシフトしてあるとします。すると各数字は16ビット下駄を履いた数値になります。

1 → 1<<16 → 65536(10)
0.5 → 1 << (16-1) → 65536(10) * 0.5 → 32768(10)
0.1 → 65536(10) * 0.1 → 6553(10)

小数の刻みは2^16分の1です。これだけの精度であれば簡単なゲームなどには使用できそうです。この場合の取り扱える整数の範囲は0〜65536です。実際の演算では次のように書きます。

例えば0.01だけカウントしていく変数があるとしましょう。カウントが10を超えたらループから抜けるような場合

unsigned int delta= (1<< 16)*0.01;
unsinged int count=0;

for(;;){

if((temp>>16)>10)break;
count+=delta;
}

別の例として、三角関数を整数で取り扱う方法を示してみましょう。2πをN_DIVS分割し、各角度でのsinの値を16ビット下駄付きで計算しておきます。

int DigitSin[N_DIVS];
for(i=0;i<N_DIVS;++i){
 DigitSin[i]=sin(i*2*PI/N_DIVS)*65536.0;
}

例えば360*(i/N_DIVS)度の方向へ1だけ座標をずらしたい場合、

x+=DigitCos[i];
y+=DigitSin[i];

となります。拙作のブロック崩しでボールの動く方向を表すために使用しています。

 

 

 

 

 

ご意見、ご感想、ご要望はこちらまで

Copyright (c) adas,2000.