まず、プログラムの内容について説明しましょう。
大きなサイズの画像データを処理します。まあ、50000×50000くらいの極めて大きな画像を扱う ことを考えてください。そして、各点には色がついています。こんな巨大な画像、ふつうの方法で はとても処理できません。ＭＢ単位ではなく、ＧＢ単位になるのですから、当然メモリ上に載るわ けがありません。
画像の圧縮が必要です。画像の圧縮には様々な方法があります。最近のファックスは２次元圧縮 をしているので、スキャナーで読み取ったデータを、約４０分の１に圧縮してしまいます。この圧 縮方法のおかげで、鮮明かつ低料金が実現されています。しかし、この２次元圧縮のやり方は、そ う簡単ではありませんし、今回のプログラムが扱うタイプのデータには向きません。
このプログラムでは、１次元圧縮という、もっと簡単な方法を使っています。これはとても簡単 な方法です。画像を、水平ラインに分け、各水平ラインについて、どの色が何ドット続いているか を記憶します。
このソフトは、簡単にいえば、お絵描きソフトみたいに、筆の色を決めて、その筆を使って巨大 なキャンバス(50000×50000)に絵を描くのです。だから、水平ラインを見ていくと、ほとんどの場 合、隣どうしは同色になり、まれにしか色は変化しません。水平方向に50000ドットあっても、実 際には500回も色が変化することは少ないのです。
ここまでの説明に基づいて、リスト１４−１を見てください。かなり分かるのではと思います。 本物のリストはもっと長かったのですが、必要部分だけをまとめ直しています。
| リスト１４−１ （低速版） |
1 #define ON 1
2 #define OFF 0
3 #define BASE_COLOR 0
4
5 extern int line_max;
6 extern int y_size, x_size;
7
8 typedef short WORD;
9 typedef unsigned short UWORD;
10 typedef long LONG;
11
12 typedef struct {
13 UWORD color_len;
14 unsigned visible:1;
15 unsigned overwrite:1;
16 unsigned mono_color:1;
17 unsigned plane:2;
18 unsigned white:1;
19 unsigned colorno:10;
20 } ELEMENT_DATA;
21 typedef ELEMENT_DATA *PELEMENT_DATA;
22
23 typedef struct {
24 LONG count;
25 ELEMENT_DATA line_data[1];
26 } LINE_DATA;
27 typedef LINE_DATA *PLINE_DATA;
28
29 WORD init_lines( lines )
30 PLINE_DATA *lines;
31 {
32 int i;
33 int j;
34 PLINE_DATA prun;
35
36 for( i = 0 ; i < y_size ; i++ )
37 {
38 prun = lines[i];
39 prun -> count = 1;
40 prun -> line_data[0].visible = ON;
41 prun -> line_data[0].overwrite = OFF;
42 prun -> line_data[0].mono_color = ON;
43 prun -> line_data[0].plane = 0;
44 prun -> line_data[0].white = ON;
45 prun -> line_data[0].colorno = BASE_COLOR;
46 prun -> line_data[0].color_len = x_size;
47 for( j = 1; j < line_max; j++ )
48 {
49 prun -> line_data[j].visible = OFF;
50 prun -> line_data[j].overwrite = OFF;
51 prun -> line_data[j].mono_color = OFF;
52 prun -> line_data[j].plane = 0;
53 prun -> line_data[j].white = OFF;
54 prun -> line_data[j].colorno = OFF;
55 prun -> line_data[j].color_len = 0;
56 }
57 }
58 }
|
| 図１４−１ 画像データの構成 |
|
|
関数init_linesは、引数で渡された巨大な画像データ用のメモリ領域を初期化します。プログラ ム起動時だけでなく、実行の途中で画像データをクリアしたいときにも呼び出されます。
引数linesは、各ラインデータへのポインタの入った配列（サイズはライン数に一致）へのポイ ンタです。言葉では説明が難しいのですが、図を見れば直ぐに分かるでしょう（図１４−１）。
アルゴリズムは超単純で、まず行数y_sizeだけループし、そのループの中で、１ライン分の処理 をします。水平ライン中で同一色が連続する部分を「要素、ELEMENT」と呼ぶことにします。 構造体LINE_DATAが１ライン分のデータです。
typedef struct {
LONG count;
ELEMENT_DATA line_data[1];
} LINE_DATA;
countは１ライン中の要素数です。各要素は、配列line_dataに入っています。この宣言では配列サ
イズが１ですが、実際にはグローバル変数のline_maxの値分だけの要素の配列に相当するメモリ領
域がちゃんと確保されています。各ラインには、line_max個の要素ELEMENT_DATAがあるのですが、
そのうちの実際に有効なデータ個数はcountに入っています。
この関数は、初期化なので、全画像データを基本色BASE_COLORにしてしまいます。したがって、 各ラインの要素は１つだけです。だから、countは１にします（39行目）。
最初のデータline_data[0]については、きちんとした値を設定します。そして、47行目からの for文中で、残りの要素をゼロクリアしています。
まず、ビットフィールドに代入するのは時間のかかる処理です。たんに整数型の代入よりも時間 がかかります。ysize = 50000, line_max = 500としたとき、内側のforループは50000×499回ルー プします。2495万回です。そして、各回にビットフィールドへの代入が６回、short型への代入が １回あります。ということは、約２億回近い代入が必要になり、極めて高速なワークステーション でも数秒は確実にかかってしまいます。
さて、このプログラム、データの初期化という単純な作業に数秒もかかっていたのでは、ユーザ には使ってもらえません。ちょっと工夫して、高速なアルゴリズムを見つけださなければいけませ ん。
このforループは、要するに、ELEMENT_DATA型の全フィールドを０にしているだけです。という ことは、prun->line[1]からprun->line[line_max-1]までのメモリ領域を０にすればよいのです。 もう簡単ですね。memsetを使って、for文を
memset( &(prun -> run_data[1]), 0, sizeof(RUN_DATA)*(run_max-1) );
に置き換えればよいでしょう。これで、一気に数十倍の速度になったでしょう。一応実用的な速度
になったはずです。
そもそも、39行目でcountに１を代入しているのは何でしょうか。有効データが１個だけという 意味なのです。だから、２個目以降のデータはゴミでもかまわないので、内側のforループはなく てもいいはずです。
もちろん、２個目以降のデータが初期化されていると、実際に次々とデータを使いだしたとき、 使用開始前にいちいち初期化をしなくて済むので、メリットが全然ないわけではありません。
リスト１４−２に、ラインの第１要素の代入ももっとエレガントにしたのを示します。
| リスト１４−２ 修正版（単純化された高速版） |
1 #define ON 1
2 #define OFF 0
3 #define BASE_COLOR 0
4
5 extern int line_max;
6 extern int y_size, x_size;
7
8 typedef short WORD;
9 typedef unsigned short UWORD;
10 typedef long LONG;
11
12 typedef struct {
13 UWORD color_len;
14 unsigned visible:1;
15 unsigned overwrite:1;
16 unsigned mono_color:1;
17 unsigned plane:2;
18 unsigned white:1;
19 unsigned colorno:10;
20 } ELEMENT_DATA;
21 typedef ELEMENT_DATA *PELEMENT_DATA;
22
23 typedef struct {
24 LONG count;
25 ELEMENT_DATA line_data[1];
26 } LINE_DATA;
27 typedef LINE_DATA *PLINE_DATA;
28
29 WORD init_lines( lines )
30 PLINE_DATA *lines;
31 {
32 int i;
33 PLINE_DATA prun;
34 static ELEMENT_DATA pattern = { 0, ON, OFF, ON, 0, ON, BASE_COLOR };
35
36 pattern.color_len = x_size;
37
38 for( i = 0 ; i < y_size ; i++ ) {
39 prun = lines[i];
40 prun -> count = 1;
41 prun -> line_data[0] = pattern;
42 }
43 }
|
この例では、どのラインの先頭要素もまったく同じなので、まずpatternという変数を用意し、 先頭要素に入れるべきパターンを作ってしまいます。color_len以外のフィールドは完全に固定な ので、初期値として設定し、color_lenだけを後で設定します。
先頭要素line_data[0]には、patternを代入するだけです。この代入文は、構造体の代入文です。 ここでの構造体のサイズはたった４バイトしかありませんが、どんな大きな構造体でも、代入文一 発で代入できます。これは忘れないでください。