行き詰った

去年の暮れに、今年は Elixir をやる!と言っておきながらいまだにやってない。それどころか、C で MD5 ハッシュ値を計算するプログラムを作っていて行き詰ってしまった。
きっかけは、MD5 の計算アルゴリズムが意外にシンプルだとを知ったこと。具体的には次のページを見たことだ。

 cf. MD5 メッセージダイジェストアルゴリズム
 cf. MD5のアルゴリズム – 数学自由研究

確かに、考えていたよりは単純な計算で、それほど引っかかるようなところもなく MD5 ハッシュ値らしい文字列を出力するところまでは実装できた(もちろん、久しぶりの C なので些細な文法ミスで引っかかるところはあったけれど)。
が、結果が合わない。試しに sample.zip ファイルのハッシュ値を、いつも使っている md5make というソフトで求めてみる(GUI のソフトだけど、<ファイル名>.md5 というファイルにハッシュ値を書き出してくれる)と:

^o^ > cat sample.zip.md5
d7db18d8239cca197c66175a8cfb0e85

これに対して、オレの書いた md5hash プログラムの出力は:

^o^ > md5hash sample.zip
ece936c4aefc960c882f49b2015aac27

となる。

コードはこのエントリに最後に載せるけど、md5hash にはデバッグのためのオプション -d-t をつけてみた。
-d オプションは、対象のファイルから読み込んだブロック(MD5 アルゴリズムは 32 ビットを 1 ワードとして、16 ワードずつ処理するのでこれをブロックと呼んでいる)を表示するオプション。データ長を 16 ワードに合わせるためのパディングなども含めて出力する。
-t オプションは、計算に使う定数テーブルを出力するオプション。
どちらのオプションの出力も、見た限りでは間違っていないように見える。
となると、あとは実際の計算をしている部分に間違いがありそうだということになるんだけど、個々の関数やその呼び出し引数をチェックしてみても、間違ったところは見当たらない。
というわけで、行き詰っている。どうしよう。
とにかく、書いたコードを載せておく。しばらくして何か思いつくかもしれない。

sqrt()関数が使えない(見つからない)

モンテカルロ法で円周率を求めるプログラムを C で書いてみたんだけど、その中で使っている sqrt() 関数が「定義されていない参照」だと言われてコンパイルできない。

takatoh@nightschool $ gcc -Wall -lm -o pi pi.c
/tmp/ccfG4PRE.o: 関数 `main' 内:
pi.c:(.text+0x81): `sqrt' に対する定義されていない参照です
collect2: error: ld returned 1 exit status

Windows の(Strawberry Perl についてた)gcc ではちゃんとコンパイルできたのに。なんで?

ダイクストラ法(2)

昨日のダイクストラ法を C でやってみた。

takatoh@nightschool $ ./dijkstra
10
0 -> 2 -> 4 -> 5

C言語:ディレクトリ内のファイルをリストアップする(2)

昨日のプログラムに、サブディレクトリのファイルを再帰的にリストアップする -r オプションをつけてみた。

takatoh@nightschool $ ./listfiles -r .
./stack/linkedlist.c
./stack/linkedlist.h
./stack/main.c
./listfiles
./fib.c
./btreesort.c
./linkedlist.c
./web_color_code.c
./strrand.c
./bmp/win-jpeg.bmp
./bmp/dog2.bmp
./bmp/bmp.c
./bmp/win-4.bmp
./bmp/win-16-1.bmp
./bmp/dog.bmp
./bmp/win-32-bf-888.bmp
./bmp/win-8.bmp
./bmp/win-32.bmp
./bmp/win-16-bf-324.bmp
./bmp/win-32-t.bmp
./bmp/win-16-t.bmp
./bmp/bmp.h
./bmp/os-4.bmp
./bmp/os-1.bmp
./bmp/win-32-bf-td.bmp
./bmp/win-1.bmp
./bmp/win-png.bmp
./bmp/win-8-td.bmp
./bmp/os-8.bmp
./bmp/os-24.bmp
./bmp/win-4-rle.bmp
./bmp/win-16.bmp
./bmp/win-32-bf-833.bmp
./bmp/Makefile
./bmp/win-24.bmp
./bmp/pic1.bmp
./bmp/win-8-rle.bmp
./bmp/bmpinfo.c
./code2rgb.c
./btree/btree.c
./btree/btree.h
./btree/main.c
./mergesort.c
./quicksort.c
./transhex.c
./heapsort.c
./filter.c
./greeting.c
./bubblesort.c
./listfiles.c

C言語:ディレクトリ内のファイルをリストアップする

readdir() 関数を使う。ファイルとディレクトリの判別には stat() 関数の戻り値(stat 構造体)の st_mode を使う。これにはディレクトリかどうかを判別する S_ISDIR マクロが用意されている。今回はディレクトリでなければファイルだと思うことにした。
あと、「.」で始まるファイル(とディレクトリ)は無視した。

実行例:

takatoh@nightschool $ ./listfiles
./listfiles
./fib.c
./btreesort.c
./linkedlist.c
./web_color_code.c
./strrand.c
./code2rgb.c
./mergesort.c
./quicksort.c
./listfiles_r.c
./transhex.c
./heapsort.c
./filter.c
./greeting.c
./bubblesort.c
./listfiles.c
takatoh@nightschool $ ./listfiles btree
btree/btree.c
btree/btree.h
btree/main.c

ビットマップ画像の情報を表示する(2)

コードを少し整理して、ファイルを分けた。あと、OS/2 のビットマップにも対応した。

実行例:
サンプルのファイルはここから拝借した。
 cf. BMP ファイルフォーマット

takatoh@nightschool $ ./bmpinfo os-1.bmp
File type          = BM
File size          = 4232 bytes
Data offset        = 32 bytes
Info header size   = 12 bytes
Width              = 200 pixels
Height             = 150 pixels
Planes             = 1
Bit count          = 1 bits/pixel
takatoh@nightschool $ ./bmpinfo win-24.bmp
File type          = BM
File size          = 90054 bytes
Data offset        = 54 bytes
Info header size   = 40 bytes
Width              = 200 pixels
Height             = 150 pixels
Planes             = 1
Bit count          = 24 bits/pixel
Compression        = 0
Size image         = 90000 bytes
X pixels per meter = 2835
Y pixels per meter = 2835
Color used         = 0 colors
takatoh@nightschool $ ./bmpinfo win-jpeg.bmp
File type          = BM
File size          = 4916 bytes
Data offset        = 54 bytes
Info header size   = 40 bytes
Width              = 200 pixels
Height             = 150 pixels
Planes             = 1
Bit count          = 0 bits/pixel
Compression        = 4
Size image         = 4862 bytes
X pixels per meter = 0
Y pixels per meter = 0
Color used         = 0 colors

ビットマップ画像の情報を表示する

ビットマップ画像の情報(サイズとか)を表示するプログラムを C で書いてみた。

参考ページ

 cf. C言語による画像処理プログラミング
 cf. BMP ファイルフォーマット
 cf. BMPファイルのフォーマット

ファイルヘッダと情報ヘッダ

ビットマップファイルには、ファイルの先頭にファイルヘッダ(BITMAPFILEHEADER)と情報ヘッダが付いているので、これを読み取って表示している。情報ヘッダにはいくつかの種類があるけど、今回のプログラムでは Windows で使われている BITMAPINFOHEADER という形式(長さ 40byte)に決め打ち。手持ちのビットマップファイルの中にはこの BITMAPINFOHEADER (ほかの情報ヘッダとは長さで区別できる)を持つファイルがなかったので、上に挙げた一番初めの参考ページから dog.bmp というファイルを拝借させていただいた。
ちなみに、情報ヘッダには次のような種類があるようだ。

  • BITMAPCOREHEADER (OS/2, 12 bytes)
  • BITMAPINFOHEADER (Windows, 40 bytes)
  • BITMAPV4HEADER (Windows 95/NT4.0, 108 bytes)
  • BITMAPV5HEADER (Windows 98/2000/Me/XP, 124 bytes)

コード

上に書いたように、情報ヘッダは BITMAPINFOHEADER 決め打ち。

実行例

takatoh@nightschool $ gcc -Wall -o bmpinfo bmpinfo.c
takatoh@nightschool $ ./bmpinfo dog.bmp
File type = BM
File size = 360054 bytes
Data offset = 54 bytes
Info header size = 40 bytes
Width = 400 pixels
Height = 300 pixels
Planes = 1
Bit count = 24 bits/pixel
Compression = 0
Size image = 360000 bytes
X pixels per meter = 1
Y pixels per meter = 1
Color used = 0 colors

Cでランダムな文字列を得る

前にも Ruby や Python でやったネタだけども。

takatoh@nightschool $ gcc -Wall -o strrand strrand.c
takatoh@nightschool $ ./strrand 20
hiVKZhO2rwtlDPUJmdo7

フィボナッチ数列を100項まで計算しようとするとunsigned long longでもたりないらしい

タイトルのとおり。

実行結果:

takatoh@nightschool $ ./fib 100
1
1
2
3
5
8
13
21
34

(中略)

4660046610375530309
7540113804746346429
12200160415121876738
1293530146158671551
13493690561280548289
14787220707439219840
9834167195010216513
6174643828739884737
16008811023750101250
3736710778780434371

最後のほうで桁が少なくなったり、明らかにおかしな数値になってしまう。

試しに Ruby でやってみた。

takatoh@nightschool $ ruby fib.rb 100
1
1
2
3
5
8
13
21
34

(中略)

4660046610375530309
7540113804746346429
12200160415121876738
19740274219868223167
31940434634990099905
51680708854858323072
83621143489848422977
135301852344706746049
218922995834555169026
354224848179261915075

ちゃんと計算できてる! Ruby すげー!

Popでエラーを知らせるにはどうする?

気がつけば1か月もあいだが開いてしまった。

さて、その1か月前のコードを眺めていて気がついたんだけど、スタックから Pop しようとしたとき、スタックが空だったらエラーになってほしい。けど、どうやったら呼び出し側にエラーを伝えられるんだろう?
Pop() の返り値でエラーを伝えることは出来ない。返り値は int 型のどんな値でも有効だから。
調べてみると errno というグローバル変数(?) に値を設定しておく、というやり方があって errno の値(整数値)でどんなエラーかを知らせるようだけど、Pop() のエラーに対応するような errno の値がない。勝手に作ってもいいもんだろうか。