というわけでアルゴリズムを昨日の仮想コードのように変更し，ビルド。JPEG を食べさせてみると・・・
やけくそにカラフルになりました。どこかを壊したっぽいです。現在格闘中。。。
ああ，こんなページがありました。
これは「クラカのプログラホーム」( クラカさん管理 ) 内の 1 ページ。クラカさんもご自分で JPEG をデコードするプログラムを書いてみたようで，氏によると，やはり量子化テーブルの読み込み方を間違え，画像が乱れていたとの事。
私も以前のコードで同じミスをしていましたが，これはとてもハマりやすい罠だと思いました。この部分を間違えていても若干画質が荒くなるだけなので，バグだとはなかなか気づきにくいのです。
ていうかそもそも，ジグザグ順に並べる意義がいまいち解せないんだけど，JPEG の仕様書にはその理由がちゃんと載っているのかなあ？ やはり手に入れておくべき？
あー，なぜか左手の力が入らないので鬱。キーの打ちすぎ？ とすると腱鞘炎？ んなワケはないか。。。
それはともかく，昨日の説明は混乱の上に混乱してしまっただけでした。デコード時には成分毎の MCU のサイズが欲しいところ。
| 色成分 | サンプリングファクタ | |
|---|---|---|
| 横方向 | 縦方向 | |
| Y 成分 | 2 | 2 |
| Cr 成分 | 1 | 1 |
| Cb 成分 | 1 | 1 |
ここで画像の大きさを 17 x 17 ドットとします。この時，画像上では 16 x 16 ドットでグリッドしたブロックが 1 つの MCU となるのは OK？ するとこの画像に MCU は横に 2 つ，縦に 2 つ存在します。
もし，これからデコードするスキャン内に 3 つの成分がコードされている場合，Y 成分においては 8 x 8 ブロッが 4 つ集まった 16 x 16 ドットのグリッドが 1 の MCU です。そして Cr および Cb 成分の MCU は 8 x 8 ドット。この MCU は横に 2 つ，縦に 2 つ存在します。
もしスキャン内に Y 成分しかコードされていない場合，Y 成分の MCU は 8 x 8 ドット。この MCU は横に 3 つ，縦に 3 つだけ存在します：決して横に 4 つ，縦に 4 つではありません。どうもプログレッシブ JPEG の AC 係数は成分別にコードされているようで，これが今回の混乱のモトというか一人で騒いでいるだけなんですが。
というか，というか，というか，もうサンプリングファクタ関連で悩んでも雑記のネタにはしたくないと思いました。リソースとしての価値が薄まってゆく〜・・・。
昨日の MCU サイズの解釈はイイ線いってたんだけど，もうちょっと混乱しているフシが。そもそもサンプリングファクタの仮定からして，なんかこう「どうしちゃったんだろう？」てな雰囲気です。あんな変則的なサンプリングファクタを持つ JPEG 画像があれば，ぜひ見てみたいものです。
スキャン内に Cr だけがある場合の MCU のサイズは 8 x 16 ドットではなくて，どうも 8 x 8 ドットと計算するようです。要するにスキャン内に 1 つしか成分が無い場合，MCU は 8 x 8 ドットだという事で。
一般形はこんな感じでどうでしょ？
スキャン内の MCU のサイズ =
8 *
スキャン内で登場する成分のサンプリングファクタの最大値 /
スキャン内で登場する成分のサンプリングファクタの最小値
なかなか，ややこしい仕様ですわん。。。
分かったです分かったです。EOB の「ランレングス」というのは，「ゼロランレングス」の拡張版でした。基本 DCT 方式ではハフマンコードをデコードして 0xf0 という値が得られた場合の「16 個」がゼロの個数の最大値でしたが，それをなるべく少ないビット数で 32767 くらいまで表現できるようにしています。基本 DCT 方式では大量のゼロが並ぶ事は稀であるため ( DC 係数がゼロというのはなかなか珍しい ) このような仕組みは必要ありませんが，プログレッシブ方式では AC 係数の (例えば) 50 番目あたりともなれば，結構な数のゼロが並んでいます。なるほどー。
ただしまだ油断はできない模様。例のライブラリを見る限り，サクセッシブ・アプロキシメーションの AC 係数のデコード中に EOB に出会うと 1 ビットずつ読みながら何かの計算をしています。一体何をやっているのやら。
それから驚愕の事実。「MCU」と呼ばれるモノのサイズ，スキャン毎に変わります。おいおいおいおい・・・。
今まで私は Y，Cr，Cb 用の 3 つのサンプリングファクタの中から最大値を選び，それに 8 をかけたものが MCU のサイズだと決め込んでいました。しかしそれは間違い。例えば次のような構成で
| 色成分 | サンプリングファクタ | |
|---|---|---|
| 横方向 | 縦方向 | |
| Y 成分 | 2 | 1 |
| Cr 成分 | 1 | 2 |
| Cb 成分 | 1 | 1 |
これからデコードするスキャンに Y 成分と Cr 成分が両方とも含まれている場合，1 つの MCU は 16 x 16 ドットと計算する事ができます。また例えば Cr 成分だけの場合の MCU は 8 x 16 ドット ( 2003-03-24追記：これは間違い )。Cb 成分だけの場合は 8 x 8 ドットを MCU のサイズとしてデコードする・・のかな？
あ，そうか。要するに SOS セグメントを処理するついでに計算しちまえばよいわけで。
で・・連休が終わってしまうような気がするのは・・とりあえず気のせいだということで。
昨日の破壊は凡ミスだったので詳細は割愛。今はプログレッシブ JPEG の EOB に悩んでいます。
例の教科書によると，EOB_n は「現在のバンドと次の n - 1 個のバンドの終了を意味する」との事。しかし，じゃあ EOB_0 は「現在のバンドと次の -1 個のバンドの終了」って事？ それでは意味が通らないので，ライブラリのソースを追いかけながらより合理的な解釈を考えています。・・が，まだよく分かりません・・。
あ，それから EOB_n の次の n ビットが「ランレングス」を表すのも謎。正確には「次の n ビット + ( 2 の n 乗) 」ですか。
というわけでアルゴリズムを昨日の仮想コードのように変更し，ビルド。JPEG を食べさせてみると・・・
やけくそにカラフルになりました。どこかを壊したっぽいです。現在格闘中。。。
突然気づいたんだけど，もしかしたらこれがデコーダの“一般形”になるのかも知れません。
// ところどころで仮想コード気味です
short Decoder::read_coeff( int bits ) {
if (bits == 0) return 0;
short coeff = (short)read_bits_scan(bits);
short sign = 1 << (bits - 1);
if ( (coeff & sign) == 0 ) coeff -= (1 << bits) - 1;
return coeff << Al;
}
void Decoder::decode_coeffs() {
// 画像にある全ての MCU について
for (int v_mcu=0; v_mcu < vertical_MCU_count; ++v_mcu) {
for (int h_mcu=0; h_mcu < horizontal_MCU_count; ++h_mcu) {
// スキャン内にあるコンポーネント数だけ繰り返し
for (int ccount=0; ccount < component_count_in_scan; ++ccount) {
int cindex = FIND_CINDEX( ccount );
short *coeff = &coeff_workarea[ cindex ][ v_mcu * horizontal_MCU_count + h_mcu ];
// 8x8 ブロックについて
for (int v=0; v < vertical_sampling_factor[ cindex ]; ++v) {
for (int h=0; h < horizontal_sampling_factor[ cindex ]; ++h) {
decode_8x8_block( coeff, cindex );
coeff += 64;
}}
}
}}
}
void Decoder::decode_8x8_block( short *coeff, int cindex ) {
// 1 つの 8x8 ブロックについて
for (int p = Ss; p <= Se; ++p ) {
HuffmanTree *tree = (p == 0)
? &huffman_trees[ 0 ][ tree_for_dc[ cindex ] ]
: &huffman_trees[ 1 ][ tree_for_ac[ cindex ] ];
bits = decode_huffman_tree( tree );
if (p == 0) { // DC 係数
dc_pred[ cindex ] += read_coeff( bits );
cof = dc_pred[ cindex ];
} else { // AC 係数
if (bits == 0xf0) {
p += 15; // ZRL
} else if ((bits & 0x0f) != 0) {
// いくつかのゼロと AC 係数
p += bits >> 4;
cof = read_coeff( bits & 0x0f );
} else {
if (基本 DCT 方式である) {
if (bits == 0) break; // End Of Block
else throw exception(); // エラー
} else { // プログレッシブ方式である
// End Of Band...
// まだよくわかんない
}
}
}
coeff[ zigzag[ p ] ] |= cof;
}
}なんか大変だー。今回のメインな関数は decode_coeffs()。そういえばリスタートインターバルも処理しないといけないんだけど，それはまた後ほど。
このままじゃネストが深くなるので，8 x 8 ブロック 1 つだけをデコードする decode_8x8_block() 関数を外に出しちゃいました。デコードされる係数は SOS で取得される Ss から Se まで。プログレッシブ方式の場合は End Of Band を処理しないといけないんだけど，これは後ほど。最後，coeff[] には or 演算で入力します。「サクセッシブ・アプロキシメーション」に対応するためですね。
関数 read_coeff() は係数を取り出すだけの単純なものだけど，符号も調整しています。それから SOS で取得した Al を用いてポイント変換も行います。小さいけど，これ重要。
今サイトにアップしている最新の JPEG デコーダのソースは 2003-02-28 ですが，今までずっと「そんなミスだけは絶対に犯さないぞ」というミスをやっちまっていました。
// jdecoder.h Decoder::~Decoder()
virtual ~Decoder(){
delete decoded_image_;
for (int c=0; c<3; ++c)
delete coeff_workarea_[c];
}
// jdecoder.cpp Decoder::segment_startOfFrame()
// デコード時の作業領域
for (i=0; i<component_count_; ++i) {
delete coeff_workarea_[i];
coeff_workarea_[i] =
new short[64 * horizontal_sampling_factor_[i] * vertical_sampling_factor_[i]];
}先生！ new[] で取得したヒープを delete で解放しようとしています！ これは本来，delete[] でなければ正常に解放されません。
でもおかしいなー，他の人は「アプリケーションの終了時にエラーが出ます〜」とか言ってソースコードをおっぴろげて，鋭い人が「new[] で取得したメモリを delete で解放しようとしてるよ」とか指摘して「あ〜その通りでした〜ありがとさん〜」という流れになるはずなのに，私の場合は何もエラー ( 例外 ) が出てきてくれませんでしたよ？ 私のことを差別すると謝罪と賠償を要ぃぇなんでもありません・・・
作業はこうなんというか，強烈な意外性もなくすんなりと進んでいます。前回までで DC 係数はデコードし終え，次には DHT が待っていました。AC 係数用ですね。
デコードを進めてみると DHT の次はもう SOS が始まります。SOS 中で取得できる「成分数」は 1。すなわちここから始まるスキャンは ( Y 用なのか Cb 用なのか Cr 用なのかは分からないけど ) 1 成分のためのものだって事。おそらく Y 成分用だとは予想できますが，どこで判断すればよいのやら？
ああ，そう言えば。。。
// ./DOC/20030228/jdecoder.cpp Decoder::segment_startOfScan()
// 1 バイト .. スキャン成分セレクタ
int component_id = (int)stream_.read8();今までずっとおざなりにしていましたが，いよいよこれを気にしなければならないようです。今までは
と決めうちしていました。そして今だって，おそらくこれから 1 ヶ月先でもこの決めうちで困ることはないと思いますが，とりあえずしっかりとポリシーを持っておかなければ。
・・でも，どの component_id がどの成分に対応しているかは，どこを見ればいいんだろう？ SOF で登場した順でいいのかな？
非プログレッシブな JPEG の SOS において，使われていない値が 3 バイトほど取得されていました。jdecoder.cpp の次の部分ですね。
// jdecoder.cpp Decoder::segment_startOfScan()
unsigned int unused;
unused = stream_.read8();
unused = stream_.read8();
unused = stream_.read8();これを次のようにして出力してみると：
unsigned int Ss, Se, Ah, Al;
Ss = stream_.read8();
Se = stream_.read8();
Al stream_.read8();
Ah = Ah >> 4;
Ah = Al & 15;
printf( "Ss = %d\nSe = %d\nAh = %d, Al = %d\n", Ss, Se, Ah, Al );それぞれの場合について，次のような出力が得られます：
非プログレッシブ JPEG の場合 Ss = 0 Se = 63 Ah = 0, Al = 0 プログレッシブ JPEG の場合 - その 1 Ss = 0 Se = 0 Ah = 0, Al = 1 プログレッシブ JPEG の場合 - その 2 Ss = 0 Se = 0 Ah = 0, Al = 0
「プログレッシブ JPEG の場合」の「その 1」と「その 2」の違いに気づきました。画像ファイルによって，Al が若干変化するようです。例の教科書によると，そのスキャンの複合後，復号できた値を Al ビットだけ左にシフトさせてやらなければならないようです。
というわけで，復号できた DC 係数を単純に Al ビットだけ左シフトしてみます。こんな画像が得られました。
前回の表示結果と見比べて見ると：
んー，今回の処理の追加でコントラストがはっきりした感じですか？ プログレッシブ JPEG ではこのように要所要所で Al に従ってシフトを行う必要があり，これをポイント変換と呼ぶようです。なんかややこしいいぃー。
えっと，以前に killer.cgi という悪用厳禁なスクリプトを書きました。私もたまにこれを使ってブラクラチェッカーのプロセスを監視し，数分間も動きっぱなしの bcc.cgi などを kill したりしています。とは言うものの一週間に 1 度のペースで気が向いた時にしか監視しないので，そんなに威張れるもんでもありませんが。
そういえばやたらと動きっぱなしのプロセスが多いのが気になっていました。$SIG{'ALRM'} と alarm() が動く事は確認できているので，このシグナルが発動する以前のブロッキング API が原因と推測。私のコードの中の該当部分はー・・・connect()？ ええ，ブラクラチェッカーは <SOCK> でソケットからデータを読み始める直前にはじめて alarm() でアラームを設定しています。そうではなく connect() の前に alarm() を呼んでみると・・・
ズバリこの部分だった模様。COARA サーバは connect() でサーバに接続できないと，いつまでも connect() を続けるようです。Windows よりもタチが悪いですよ？ とツッコミを入れるべきマジレス。
プログレッシブ JPEG の資料が全く見つからないし，例のライブラリのコードも読みにくいし，・・・さてこれからどうしたものか。ああ，今日もコードを眺めるだけで終わってしまいそうです。
ところで
for (int a=0; a<10; +a)
...;こんなコードのコンパイルに成功しないでください＞コンパイラ各位 (ρ_；)
VC++5.0 および gcc 3.2，いずれもこんなコードを警告なしに通してしまいます。今日は早いうちに電波を受信したため嵌りはしませんでしたが，市場に出回っているソフトウェアの中で，どれくらいの製品にこのようなコードが紛れ込んでいるやら・・・。
昨日はブラクラチェッカーの方で一日つぶれてしまったので残念。JPEG デコーダ，なかなか前に進みません。
そんな中でグッドニュース。なんとかデコードできた MPEG 画像を繋ぎ合わせ，それなりの動画を観る事に成功しました。一歩ずつ前進しております。
・・そんな中でバッドニュース。On2 社のオープンコーデック "VP3" での作業を押し付けられました。曰く「再生時，コマがカクカクして仕方がない。デコード速度は太刀打ちできないだろうから，ウィンドウへの描画速度を上げる事でなんとかならないか」との事。とりあえず描画せずにデコードのみの時間を計測して愕然としました。描画させていないのに，すでにデコードだけで目標の時間を超えてしまいます。一体私にどうしろと。
不覚にも 2003-03-13 の雑記を書かないまま日付を越してしまいましたが，でも 2003-03-13 に起こった出来事なので書いちゃえーい。いや，本当にビビったんですってば。
とある方からブラクラチェッカーの RFC 違反を指摘いただき，修正していました。そこでどうせだから HTTP のゲット処理をよりエレガントなものにしようと考えたのです。最近 HTTP プロクシの製作に熱を上げていたので作業はすんなり終了。ローカルでのテストも済ませて COARA サーバにアプンしました。
んー，データを取得しないんですが。
しかし幸いにもここでプログラマの勘が発動。今までは <SOCK> を使ってデータを読んでいたんだけど，今回はちょっとカコつけて recv() を使ってみました。おそらくそれが間違いだったのでしょう。どうせどちらでもほぼ意味は変わらないので <SOCK> に戻し，COARA に再びウプ。事なきを得ました。
COARA の CGI サーバは以前から gethostbyaddr() によるホスト名の逆引きを停止していました。サーバに無駄な負荷がかかりますもんね。しかしまさか recv() まで使えなくなっていたとは。<SOCK> とはどう違うんだろう？
あ，ちなみに今まで Transfer-Encoding: chunked の時の処理にバグがあって，ALRM シグナルが送られるまで 20 秒間プロセスが固まっていたのは内緒です。じゃなくてごめんなさい。・・・いつか本当に営業妨害か何かで訴えられる予感・・・。
なんとか ( 凡ミスが続いてヘンなところでつまづいて悩んでたけど ) DC 係数は全てデコードできました。
私は面倒臭がりなので，初期段階では Y 成分しか表示しません。とりあえずビットストリームのデコード中に変な例外さえ出なければよいのです。で，表示させたのがこんなの。
( 完全に著作権 (著作同一権) の侵害ですが，気にしないように :-)
これは IJG のアーカイブの中にあったバラの絵の DC 係数を展開し，Y 成分だけ表示させたもの。かなり暗めに見えるのが不思議でたまりませんが，もしかしたら間違ってる？ ・・いや，おそらく間違いではないとは思いますが。。。
最近の cppll の議論を眺めていると，自分の経験のなさを改めて実感します。「パソコン」なるものに出会って 10 年も経つのに，私は未だにその費用を回収していないってわけですか。ファイト，自分。
件の JPEG デコーダの中で，こんな関数を使っています。
static inline void _bezero(void *m, unsigned int size) {
unsigned long *im = (unsigned long *)m;
unsigned char *cm;
while (size >= sizeof(unsigned long)) {
*im++ = 0;
size -= sizeof(unsigned long);
}
cm = (unsigned char *)im;
while (size--)
*cm++ = 0;
}サイズが size バイトのメモリ m のビットパターンを 0 にします。size が unsigned long のサイズよりも大きい間は unsigned long 分のサイズだけ一気に処理してしまうのが特色 ( 常套手段，とも言います。わらい )。・・こんな関数を使うくらいなら memset() を使うべきだとツッコミも入るもんですが，気にしちゃいけません。私ですから。
cppll の議論によるとこのコードはどの環境でもうまく動くとは限りません。というのも，この関数は m のアラインメントを特に気にしていませんが，なんと中途半端なアラインメントの部分を unsigned long などとキャストして値を書き込んだりすると，クラッシュしてしまう環境があるのです。ええっと「バスエラー」が出るんでしたっけ？
少なくとも私はあまり縁がありそうにないマシン上での話でしたが，なかなかに恐怖。sizeof(unsigned long) のあたりいかにも高い移植性を狙ってますが，あじゃぱー。
bzero() のパクリ。・・これって ANSI-C じゃないですよね？会社での MPEG デコーダの製作ですが，なんとか motion vector の取得にも成功しました。これで，画像の取得に必要な全てのビットストリームは高い確率で正常にデコードできていると考える事ができます。
で JPEG の方は・・だめっすねー。例の IJG のライブラリのソースを追いかけるしか無い状態ですが，辛いー。
きっと昨日の悩みはアホみたいな悩みだったと思うんです。持続的接続をキメている以上，少しくらいの沈黙は覚悟するべきなんです。でもまあ，あまり長時間に亘って何もしない接続を保っているのもアレなんで，それを制御するのが Keep-Alive ヘッダ。えーと，Mozilla の出力によると，
Keep-Alive: 300
300 ? ・・・秒？・・・。
・・・いつも Mozilla はそんなに長い接続をサーバに要求してるのかな・・・。Keep-Alive は HTTP/1.1 ヘッダのはずなんですが，そして確かに RFC2616 に Keep-Alive という言葉は登場しますが，そのシンタックスを明示したリソースが見つかりません。一説，"Keep-Alive: <名前>=<値>..." のように「名前」と「値」を '=' で結びつける書き方が正式だとも聞いたような。これは WWW の七不思議のひとつとカウントしてよろしいか？
乗りかかった船なので，もう少し脱線です。頭の体操がてらに HTTP プロクシを作っていると，もはや「体操」レベルじゃなくなって「なんたら選手権」レベルになってしまいました。つまり本格的なモノが出来ちゃったです。
今悩んでいるのが Mozilla の挙動なんですが：HTML をパースするのが Mozilla の仕事である以上，その持続的な接続の中で，あとどれくらいのリソースを GET するかは Mozilla が決めるべき事。サーバはきちんと HTTP/1.1 の仕様に則ってずっと接続を保ったまま次のリクエストを待っているのに，Mozilla はやはりプロクシに接続したまま沈黙を始めてしまいます。一体プロクシに何を期待してるんだろう？
というわけで"壁"に激突しました。JPEG の方にとりかかろうっと。