雑な k|m の生態について

突然ですが，簡単な JPEG のデコードと表示に成功しちゃいました。

->今日の成果物；

このうち app.h にある AppBase クラスは，普段ちょっとグラフィックを扱いたい場合に使っているものです。内部ではウィンドウ，DIB セクション，スレッドを持ち，run() メソッドはメッセージループです。スレッドを用意しているお陰でメインの処理を細切れにせずに済むわけですね。これはゲームやデモを作る場合には常套手段？ ですか？

さてこのコードは識別子 _MT が定義されていなければコンパイルできないようになっています。しかしただ単に #define _MT とやったって，生成されたプログラムは正常に動作しないはずです。これらのコードを VC++ でコンパイルするには「プロジェクト - 設定」と辿り，「プロジェクト設定」ダイアログを出します。

「カテゴリ」を「コード生成」とし，「使用するランタイムライブラリ」を「マルチスレッド」にします。Win32 Debug の時は「マルチスレッド(デバッグ)」ですね。

なお今日は成果物内に実行ファイルもつけておきました。jdec01.exe は同じディレクトリに置いてある test.jpg を正しくデコード，表示する事が出来ます。ただ，何となく色がヘンなんですよね。そこらの JPEG 画像を test.jpg とリネームして jdec01.exe で表示させてみると異常さがよく分かります。おそらく原因は IDCT の誤差が激しいか，逆量子化のやり方を間違えているかのどちらか。この壁は厚そうです。

とまあ，HuffmanTree 構造体をリスト構造のようなものにし，malloc() を用いて必要なメモリのみを消費するようにするための関数を書いてみました。

// テーブルから木に変換するコード
static
HuffmanTree *make_blank_branch() {
  HuffmanTree *blank = (HuffmanTree *)malloc( sizeof(HuffmanTree) );
  blank->next_tree[0] = NULL;
  blank->next_tree[1] = NULL;
  blank->value[0] = 999; // こんな値が取得されたらエラー
  blank->value[1] = 999;
  return blank;
}

static
int make_huffman_tree( HuffmanTree *root,
                       HuffmanTable *src_table, int table_size )
{
  int code, bits;
  int i, b;
  HuffmanTree *next_tree, *current_tree;

  // 木を生成してゆく
  for (i=0; i<table_size; ++i) {
    code = src_table[i].code;
    bits = src_table[i].bits;
    current_tree = root;

    while (bits--) {

      if (bits == 0) {
        current_tree->value[code & 1] = i;
        break;
      }

      b = (code & (1 << bits)) ? 1 : 0;
      next_tree = current_tree->next_tree[b];

      if (next_tree) {
        current_tree = next_tree;

      } else {
        // 新しく枝を生成する
        next_tree = make_blank_branch();
        current_tree->next_tree[b] = next_tree;
        current_tree = next_tree;
      }
    }
  }

  return 0; // noerror
}

// ハフマン符号を，木に従ってデコード
static
unsigned int
decode_huffman_tree( JPEGDecoder *jd, InputStream *is, HuffmanTree *tree ) {
  unsigned int b;
  HuffmanTree *next, *current = tree;

  while (1) {
    b = read_bits_mcu( jd, is, 1 );
    next = current->next_tree[b];
    if (! next) {
      return current->value[b];
    }
    current = next;
  }

  // unreachable
  return 999;
}

2002-12-26 や 2002-12-27 のコードと比べてどうなんでしょうね？ ほんのわずかに高速な気もしますが，どうでもいい程の速度だとの声も。笑い

なお，JPEG の全体のデコードが終われば木の要素を free() する作業が待っています。おそらく再帰を使えば簡単ですが，それでスタックを食いつぶしてアプリケーションがトホホな事にならない事を祈らなければ。多い場合は 16 段ほど木を伝っていくはめになると思われます。

さて，基本的な JPEG のデコードはおそらく上手くいくと思うので，明日からは実際に視覚的に出力したいと思います。ここからはちょっとの間 Windows 限定の話題が多くなってしまいますが，ご愛嬌です。

すっかり風邪を引いてしまいました。今日で 3 日目突入。もうすぐ新年なのに何やってるんだか。。。

風邪を引いた時はスポーツドリンクを飲んで凌いでいますが，糖分が多いので素人にはオススメできません。まあ素人はあれだ，ミカンでも食べてビタミン C を補給しなさいってこった。でもビタミン C って防酸化剤の名目でどんな食品にも大量に入ってますよね。。。

というワケで JPEG デコーダ作製が止まっちゃいました。そう言えば前回「HuffmanTree * 型を保持すれば良い」とか書いてますが，実はこれはあまり気が進まないんですよね。というのも，この設計はすなわち，新しく木を接続するために malloc() が必要になるという事を意味します。しかも本番 = 動画を扱う場合はもはやハフマン符号は固定されているため，木のサイズは不定ではありません。要するに本来は巧くすればメモリ管理は全部ヒープ上で行えるわけで，malloc() なんて出来る限り使いたくないわけで。

あー，とにかく養生しないと，書けるコードも書けません。以上。

このようなハフマン符号のデコードにも問題がないわけではなくて

資源を余計に使う

私はシビアな環境でコードを書く必要に迫られた事はないんですが，でもまだまだ 1 バイトも無駄にできない環境も存在するらしいですね。このデコードの方法では

• ハフマンテーブルを木に変換するコードが必要
• ハフマン木の構造体はハフマンテーブルの構造体に比べて大きい

の 2 点で，リソースが若干大目に必要になります。

どれだけのハフマン木の配列が必要なのか？

2002-12-24 のコードではこっそりと配列の要素を 512 個用意していますが，まったくのあてずっぽうです。ハフマンテーブルならば 256 個を超えて必要になる事はありません。ハフマン木はその 2 倍程度かなとも思ったんですが

0 .. 11110
1 .. 11111

のような ( 非常に非効率的だけど，不可能ではない ) ハフマン符号の場合

#define ERROR 999
HuffmanTree tree[] = {
 /* next_index[0], next_index[1], value[0], value[1] */
  {  0,             1,             ERROR,    ERROR },
  {  0,             2,             ERROR,    ERROR },
  {  0,             3,             ERROR,    ERROR },
  {  0,             4,             ERROR,    ERROR },
  {  0,             0,                 0,        1 }
};

// HuffmanTree::parent は無視しました

という木を生成したくなります。この時，配列には 5 つの要素が必要です。元のハフマンテーブルから必要な木の容量を計算できれば悩む必要はあまりありませんが，ここのトコロ，どないやねんね？

あ，分かった(わらい)。HuffmanTree::next_index[] は次の要素のインデックス値を示す整数型ですが，これをやめて HuffmanTree * 型を保持すれば良いんですね。HuffmanTree の設計をこう変えれば

typedef struct _huffmanTree {
  struct _huffmanTree *next_branch[2];
  struct _huffmanTree *parent;
  unsigned int value[2];
} HuffmanTree;

あー，急遽 2002-12-26 を書き直したくなりました。ちょっと書き直してきます。

最近なぜか起床後 6 時間あたりの眠気が異常です。春の陽気のようにね。今週はもう終わりですが来週からどうしたもんかと悩み中。カフェインドロップを首筋から動脈注射ですかっていうか来週は会社は休み？ 今日で仕事納め？ ウッソでー。騙されません勝つまでは。

そうだ，今日はデコード時のコードを示す日です。昨日のコードで生成したハフマン木を用いてビットストリームをデコードするには，こんなコードを書きます。

unsigned int
decode_huffman_tree( JPEGDecoder *jd, InputStream *is, HuffmanTree *tree ) {
  unsigned int b;
  int idx=0, next_idx;

  while (1) {
    b = is->read_bits( is, 1 ); // 1 ビット取得
    next_idx = tree[idx].next_index[b];
    if (next_idx == 0) {
      return tree[idx].value[b];
    }
    idx = next_idx;
  }

  // unreachable
  return 999;
}

このコードは充分に速い上にビットストリーム内のエラーを簡単に把握する事ができ，要するに JPEG や一般的な動画を扱う上でかなり優秀だって事です。ただしデメリットもないわけではなくて。。。( 続く )

よく考えたらここでコードを掲載してもあまり役立つ事は少ないわけで，ちょっと不毛な感じもしてきましたが，しかし今さら気にしません。

// 未使用の枝を探す
static
int find_blank_branch( HuffmanTree *tree, int size, int offset) {
  int k;
  for (k = offset; k<size; ++k) {
    if (tree[k].parent == -1) {
      return k;
    }
  }

  fprintf(stderr, "fatal error!");
  exit(1);

  return -1;  // unreachable
}

static
int make_huffman_tree( HuffmanTree *dst_tree, int tree_size,
                       HuffmanTable *src_table, int table_size )
{
  int idx, next_idx, blank_idx;
  int code, bits;
  int i, b;

  // ハフマン木の parent の初期値は -1 = 未使用な枝を表す
  //       value の初期値は 999 くらい = こんな値が取得できたらエラー
  for (i=0; i<tree_size; ++i) {
    dst_tree[i].next_index[0] =
    dst_tree[i].next_index[1] = 0;
    dst_tree[i].parent = -1;
    dst_tree[i].value[0] =
    dst_tree[i].value[1] = 999;
  }

  // 木を生成してゆく
  for (i=0; i<table_size; ++i) {
    idx = 0;
    code = src_table[i].code;
    bits = src_table[i].bits;

    while (bits--) {

      if (bits == 0) {
        dst_tree[idx].value[code & 1] = i;
        break;
      }

      b = (code & (1 << bits)) ? 1 : 0;
      next_idx = dst_tree[idx].next_index[b];

      if (next_idx != 0) {
        idx = next_idx;

      } else {
        // 未使用の(枝となる)バッファを探す
        blank_idx = find_blank_branch(dst_tree, tree_size, idx+1);
        dst_tree[idx].next_index[b] = blank_idx;
        dst_tree[blank_idx].parent = idx;
        idx = blank_idx;
      }
    }
  }

  return 0; // noerror
}

関数 make_huffman_tree() は構造体 HuffmanTable を構造体 HuffmanTree に変換します。それぞれの構造体の設計については 2002-12-24 参照です。

概念を確認するため，次のようなハフマンテーブルを考えます。

ハフマンテーブル

値	ハフマン符号
0	1010
1	00
2	01
3	100
4	1011

これをデコードする「木」は次のような形になります。今回の「再考」シリーズは，上のテーブルから下の形の「木」( 木に見えないのはご愛嬌 ) を生成するのが主なネタ。

ハフマン木

インデックス	next_index[0]	next_index[1]	value[0]	value[1]
0	4	1
1	2
2	--	3	3
3	--	--	0	4
4	--	--	1	2

ここでビットストリームに 100001011 が流れてきました。木を辿りながらこれをデコードして行きます。

• 現在のインデックス = 0
• 1 ビットを読み，"1" を取得
• next_index[1] を参照，現在のインデックスを更新 = 1
• 1 ビットを読み，"0" を取得
• next_index[0] を参照，現在のインデックスを更新 = 2
• 1 ビットを読み，"0" を取得
• next_index[0] を参照，無効なインデックスが取得されたので value[0] = 3 を返す
• 現在のインデックス = 0
• 1 ビットを読み，"0" を取得
• next_index[0] を参照，現在のインデックスを更新 = 4
• 1 ビットを読み，"0" を取得
• next_index[0] を参照，無効なインデックスが取得されたので value[0] = 1 を返す
• 現在のインデックス = 0
• 1 ビットを読み，"1" を取得
• next_index[1] を参照，現在のインデックスを更新 = 1
• 1 ビットを読み，"0" を取得
• next_index[0] を参照，現在のインデックスを更新 = 2
• 1 ビットを読み，"1" を取得
• next_index[1] を参照，現在のインデックスを更新 = 3
• 1 ビットを読み，"1" を取得
• next_index[1] を参照，無効なインデックスが取得されたので value[1] = 4 を返す

ビットストリーム 100001011 は 3 1 4 とデコードできる事を確認しました。・・・とここでテーブルを木に変換するコードを載せたかったんだけど，スペースが足りないのでまた明日。1 日の雑記であまりに大量の情報を載せると，後を続けづらくなるのです。

はい，予告通りハフマン符号のデコードについて考えてみます。現在のデコードのアルゴリズムはこんな感じ：

typedef struct _huffmanTable {
  unsigned int code; // ファイルに記録されているコード
  unsigned int bits; // ファイルに記録されているコード長
} HuffmanTable;

// 実際にこんな宣言をしているわけではないけど
HuffmanTable table[256];

• 読み込んだビット数 = 0
• 読み込んだ値 = 0
• ここから繰り返し
• 1 ビット読み込み / ここで「読み込んだビット数」が 1 つ増え，「読み込んだ値」が更新される
• ここから繰り返し / 変数 v を 1 ずつ増加
• v 番目のテーブル table[v] のメンバ bits が「読み込んだビット数」に等しく，メンバ code が「読み込んだ値」に等しければ・・
• -> v を戻り値として終了
• 繰り返し終了
• 繰り返し終了

DHT セグメントで定義されたデータをそのまま用いる場合，このアルゴリズムはかなり単純です。大量のイメージでも扱わない限り，充分に実用的なんじゃないかな？ しかし今私が目標にしているのは動画。1 秒間に少なくとも 10 枚以上デコードできなければ使い物になりません。より速いアルゴリズムを追い求める必要があります。

上記のアルゴリズムはなんていうか，「ストリームから 1 ビット読み込み，テーブルを全部嘗める！ そしてついに目的の値をゲットォォ！！」というやや強引な方法。しかしそもそもハフマン符号はよく「ハフマン木」として説明されます。そのものズバリ，ストリームから 1 ビット読み込む毎に行う操作は「枝を辿る」のみ，そして「気づいたら葉にゴールしてた」てな復号アルゴリズムがちゃんと存在します。というよりも大学なんかで教わるとしたら，このアルゴリズムしか教わらない気もします。復号時のアルゴリズムのイメージはこう：

typedef struct _huffmanTree {
  int next_index[2];  // 木を辿るためのインデックスを保持
  int parent;         // テーブルを木に変換する時に使う
  unsigned int value[2];  // 目的の値が格納されている
} HuffmanTree;

HuffmanTree tree[512];

• 木の現在のインデックス = 0
• ここから繰り返し
• 1 ビット読み込む
• 読み込んだビットで木を辿ってみる / 具体的には，現在の木 tree[現在のインデックス] のメンバ next_index[読み込んだビット] を得て，「次のインデックス」とする
• 辿れなければ・・ / 具体的には，次のインデックスが無効なものならば
• 現在の木のメンバ value[読み込んだビット] を戻り値として終了
• ここで現在のインデックスを次のインデックスに更新する
• 繰り返し終了

復号を行う前に DHT で得られたハフマンテーブルを「木」に変換するわけですが，具体的なコードはまた明日。

-> 本日の成果物；

そういう気はしてたわけですが，やはりそうでした。凡ミス。逆量子化を行い IDCT をかけた YCrCb を一枚の MCU にまとめる部分でなぜか難しいコトをやっていたのを，単純で簡潔で且つちょっと速く書き直したらもう解決ですかコラ。特筆すべき部分はありませんというか，ネタにも何にもなりゃしませんでした。

今日のコードは 2002-12-21 の test.jpg を正しくデコードします。実行すると数字がズラッと表示されますが，そのうち左上 8x8 個の数字を抜き出すとこんな感じ。

ffffff ffffff ffffff ffffff ffffff 000000 ffffff ffffff
ffffff fefefe fefefe ffffff 000000 000000 ffffff ffffff
ffffff ffffff fefefe 000000 ffffff 000000 ffffff ffffff
ffffff ffffff ffffff 000000 ffffff 010101 ffffff ffffff
ffffff ffffff 000000 ffffff ffffff 010101 ffffff ffffff
ffffff 000000 000000 000000 000000 000000 ffffff ffffff
ffffff 000000 ffffff ffffff ffffff 000000 ffffff ffffff
000000 ffffff ffffff ffffff fefefe 000000 ffffff ffffff

おし，ちゃんと A の字が見えます。

仕方がないので明日の予告。ハフマン符号の復号アルゴリズムについて再考します。今は 1 ビット取得する毎にテーブルの符号と符号長を全部比較していますが，こんなのは無駄。もう少しスマートなアルゴリズムが存在するわけで。

経産省、オープンソースをより推進 ( /.-J )

というよりも，私としては LZW や MPEG などのライセンス料をなんとかして頂きたいなと。かねてからの LZW 問題や MP3 問題，JPEG 問題などで観察出来ますが，プログラムを書く事やそれを配布する事に何らかのコストがかかる場合，私たちは可能な限りそれを回避しようとします。間違っても，素直にライセンス料を払ったりはしません。

LZW

米 UNISYS が「辞書」を用いた LZW 圧縮アルゴリズムについてライセンス料の徴収を開始。元々はフリーで使用する事を認めていたんだけど，その好意を悪用した企業が出てきたからでしたっけ？ ( <- 裏は取れていません ) これに対抗するために PNG 画像形式が登場。内部で用いる圧縮アルゴリズムは deflate 圧縮 ( = LZ77 + ハフマン符号化 )。

MP3

MP3 のプレイヤにもライセンスが必要とアナウンスがあった時には，フリーウェア界隈に衝撃が走りましたとも。これにより「午後のこ〜だ」が一時配布中止に。対抗手段として「午後のこ〜だ」はソースファイルとコンパイラを配布。また対抗ファイル形式として Ogg が登場。

JPEG

データ内に連続している 0 の個数をカウントし，その個数をファイルに格納する事でデータ量を抑えるのが「Zero-Run-Length」。こんな簡単な発想にも特許を取得されていたのは驚きでしたが，どうやら日本ではその特許は無効であるらしい事が判明。ほっと胸を撫で下ろしています。

MPEG

確かにライセンス料の徴収も分かりますが，しかし私たち貧乏人はなるべく開発コストを抑えなければなりません。対抗できる動画コーデックとして VP3 が台頭しそうですが，いまいちライセンスが不明瞭かと？？ GPL だったらちょっと避けたいです。個人的に。

技術者を保護する目的で存在していた「特許」，近頃はめっきり風あたりが強くなった模様。国内のソフトウェア産業を活性化させるならば，開発者がこのようなくだらない問題にブチ当たった時に，なんかこう，アレがあればいいんじゃないかなと。

疲労度：1434

・・・ダメです。完全にドツボです。何が悪いのかさっぱり分かりません。こういう場合に一番怪しいのはハフマン符号を復号する部分なんだけど，でもちゃんと正しく動いてるしなあ。。。

つまりサンプリングファクタの解釈はこんな感じでよいのかと。平常時における「MCU にまつわる各種の値」はサンプリングファクタを取得した直後に計算しておきます。そしてそれぞれの MCU をデコードする時において，画像の右端や下端に到達した時は状況に応じた「MCU にまつわる各種の値」を計算します。・・・なんか汚いなあ。

-> 本日の成果物；

とりあえずサンプリングファクタ周りは終了ですかね。で，このコードは，上のディレクトリに置いてある test.jpg を正しくデコードしません。次はどこが悪いんだろう。。。

昨日からの続きなんですが，つまりこんな感じで MCU をデコードしなければなりませんか：

• 普通は SOF0 から採取されたサンプリングファクタを元に MCU の個数を算出し，デコードを行う
• 画像の右端または下端に来たら，残りの画素数から構成され得る 8x8 ブロックの個数を数え，それを MCU の数とする

私はこういうのが苦手だという事がハッキリしました。別に難しくはないんだけど，面倒くさいのです。

それから「サンプリングファクタ」自身についての誤解も判明。サンプリングファクタは，単純に「MCU を構成する 8x8 ブロックの数」でよかったんですね。私はここを難しく考えていて，

サンプリングファクタ
  輝度成分 Y  水平方向  2
              垂直方向  2
  色差成分 Cb 水平方向  2
              垂直方向  1
           Cr 水平方向  2
              垂直方向  1

Y 水平方向，Cb 水平方向，Cr 水平方向の比率が同じため，MCU の横幅は 8x8 ブロック 1 個分 = 8 ドットになるんだと考えていました。なんでこんな勘違いをしていたのか，今となっては・・もう分からないです。。。

とりあえずサンプリングファクタの理解に関する問題点は出揃ったんで，このあたりのコードを修正しなければなりません。・・なんだか作業が異様に遅いですが，それは「貧乏暇なし」だからかと。

次の非常に小さな JPEG ファイルは，多くのグラフィックビューアで正常に見る事が出来ます。無論，JPEG ファイルとして当然正しいものです。

このファイルで私が辟易している理由は，そのプロパティにあります。

横幅  8 ドット
高さ  8 ドット

サンプリングファクタ
  輝度成分 Y  水平方向  2
              垂直方向  2
  色差成分 Cb 水平方向  1
              垂直方向  1
           Cr 水平方向  1
              垂直方向  1

サンプリングファクタは SOF0 から採取されます。昨日アップロードしたファイル jdseg.c の make_extradata_SOF0() 関数は，得られたサンプリングファクタから後の処理に用いる値を算出しています。ここで上の JPEG ファイルでは，1 つの MCU にある 8x8 ブロックは全部で 6 個と算出されます ( Y 4 個，Cb 1 個，Cr 1 個 )。また 1 つの MCU の横幅は 16 ドット ( Y が横に 2 個並ぶため )，高さが 16 ドット ( Y が縦に 2 つ並ぶため ) と算出しています。

それが大きな間違いでした。確かにサンプリングファクタだけを見ればそれは正しいのですが，画像のサイズを良く見ると 8 ドット x 8 ドット。計算上の MCU よりも小さいのです。

この場合，MCU には Y 1 個，Cb 1 個，Cr 1 個のブロックしか入っていません。かといってサンプリングファクタが完全に無視されるわけでもなく，Cb，Cr ブロックはきちんとデコード後にサイズを 2 倍にしてやる必要があるようです。

やばい。また混乱し始めています。