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

別に私が見つけた技でもないし，多くの人に言われてみれば「まぁそういう事も出来るだろうな」で済む事なんですが，私にはちょっと衝撃的なコードだったので紹介。勝手に転載してるので著作権法的にヤバいんですが，どうせ私には失うモノはありません。

VC++ML で「オーバーフローを検出するには」というネタが。アセンブラならオーバーフローフラグを見れば良いわけですが，C や C++ ではどうすべきか？ という事で，ryoji さんという方が提示したコードがこう

#include <limits.h>

int __fastcall mulInt(int argA, int argB)
{
    int iAB;

    iAB = argA * argB;
    __asm jo l_overflow;
    return iAB;

l_overflow:
    return (((argA ^ argB) & 0x80000000) >> 31) + INT_MAX;
}

普通にアセンブリコードを混ぜちゃえば良いんですね。このコードではオーバーフローが起きた場合，INT_MAX もしくは -INT_MAX が返ります。最後，l_overflow ラベル以降の部分ではトリッキーなコトをしていますが，要するに argA と argB のどちらか片方だけがマイナスの場合，INT_MAX にマイナス符号をつけています。芸が細かいです。

私的には INT_MAX * INT_MAX を計算して INT_MAX が返ってくると鬱になるので，例外を投げようと思いました。

int __fastcall mulInt(int argA, int argB) {
    int r = argA * argB;
    __asm jo l_overflow;
    return r;

l_overflow:
    throw "overflow!";
}

ん，ナイスでイカスです。ていうかいい加減に例外で const char[] を投げる癖は直せ＞自分 ・・・便利なんでつい・・・。

NegativeCoding シリーズでは，コーディング中に出会ったおバカなコードを紹介したりしています。・・とは言うもののあまりネタが発掘される事はないんですが。

今日は C のプリプロセッサによるおバカなトリック。思いつく私もアレだけど，期待通りにヤっちゃうコンパイラもアレだよなーと。。。

#define SLASH /

SLASH* comment */

int main(int ac, const char *av[]) {
  return 0;
}

VC++5.0/6.0 限定ですが，通しやがりました。SLASH* comment */ は完全にコメントとして扱ってくれています。これをふんだんに用いる事で，SLASH 型へのポインタ変数の宣言と偽りコメントを残す事が出来てダイイングメッセージに便利。

NegativeCoding ダメ，ゼッタイ！

私は会社でコードレスなマウスを使っています。元々会社の押入れに転がっていたもので ( 実は部長の私物であった事を今日知った )，PS/2 端子にはターミナルのような物を接続し，マウス本体に単 4 の電池を 2 本入れます。それだけに重量感抜群。机から落としたら確実に逝きます。

今日，いよいよマウスの電池が無くなった模様。半年に 1 回は交換しているようなペースで，半端にエコロジー厨房の私はいたく気になっていました。そろそろこのマウスともサヨナラすべきかと。

今のところ私がオススメなのは A4TECH のマウス。ローラーが二つあり，なんとなくこう，微妙に使い分ける事が出来ます。また人差し指＝左クリック，中指＝右クリックの他に親指，薬指部分にもボタンがあり，クリックするとフシギなウィンドウメッセージを送出してくれます。

・・あ，このネタは面白い方向に拡がるので，また後日にしようっと。

VC++5.0 では無理だろうなと思っていた「テンプレートの特殊化」ですが，テンプレートの引数が int 型の場合は普通に出来ちゃいました。

#include <stdio.h>

template<int N> class fibo {
  public: enum { value = fibo<N-1>::value + fibo<N-2>::value  };
};

template<> class fibo<1> { public: enum { value = 1 }; };

template<> class fibo<0> { public: enum { value = 0 }; };


int main() {
  printf("2 %d\n", fibo<2>::value );
  printf("3 %d\n", fibo<3>::value );
  printf("4 %d\n", fibo<4>::value );
  printf("5 %d\n", fibo<5>::value );
  printf("6 %d\n", fibo<6>::value );
  printf("7 %d\n", fibo<7>::value );
  return 0;
}

よく引き合いに出される「フィボナッチ数列」。出力結果はこんな感じ。

2 1
3 2
4 3
5 5
6 8
7 13

あと，正方行列のクラス作って逆行列を求めたりして遊んだりしました。普通の C++ 使いには「ふーん。で？」てな話ですが，VC++5.0 使いな私にはかなり感動ですよ？

いつまでもコードを「眺めている」だけでは何も解決しないわけで，ライブラリをコンパイルして動作を実際に見てみることにしました。参考 -> Independent JPEG Group；

目的はデコードの動きを把握する事。アーカイブの中に main() が書かれたファイルはいくつかありますが，djpeg.c をコンパイルします。これをコンパイルするために何が必要なのかがわからなかったので，とりあえず全てのファイルをプロジェクトに詰め込んじゃいました。

どうやら jconfig.h というファイルが足りない模様。アーカイブの中にいくつか jconfig.* というファイルがありますが，そのうち "jconfig.vc" を jconfig.h とリネームしました。それからわけもわからずに詰め込んだファイルの中でいくつか main() が定義されていたので，djpeg.c 以外で main() を含むファイルをプロジェクトから外します。また jmem***.c は，jmemansi.c と jmemmgr.c 以外をプロジェクトから外します。

要するに，よくわかんないけどコンパイルが通るようにしちゃえって事で。

早速，コンパイルできた実行ファイルを使ってみます。

E:\DJPEG\Debug>djpeg -bmp input.jpg output.bmp

input.jpg は私のコードでは正常にデコードできずに悩んでいる画像。やはり正常に output.bmp にコンバートする事ができてます。

これをデバッガで追いかければ，私のコードのどこが悪いのかが分かる。。。かな？

JPEG に詰まっているので“頭の体操”がてらに HTTP プロクシを作ってみたりしていますが，最初の難関発生。「持続的接続」がらみなんだけど。。。

「持続的接続」について細かい事は省略。クライアント ( Mozilla さん ) は，例えば www.goo.ne.jp の HTML のパース中に ad.goo.ne.jp のイメージを見つけると，その接続の中で ad.goo.ne.jp へのリクエストをしやがります。

「持続的接続」ってのは一つのホストのみに通用するものかと思ってましたが，それはただの勝手な思い込みだった模様。さすが，一筋縄ではいきません。

会社では部長が OpenDivX と格闘しています。しばらくは金にならない仕事なのになぜ彼はそこまで頑張るよ。。。

動画の符号化/復号化はまんま OpenDivX に任せっきりですが，どうしてもあらかじめ用意されていた YCrCb -> RGB 変換ルーチンが上手く動かないらしく，どこか他のコードから持ってきたとの事。その結果，再生してみるとどうも赤みが足りないというか，全体的に薄い色になってしまいました。

結局 RGB -> YCrCb 変換ルーチンと YCrCb - > RGB 変換ルーチンの係数に整合性がなかった事が判明，そこを修正する事で完璧な色になるはず。実際に試して見ると変わりませんでした。そう言えば RGB -> YCrCb 変換ルーチンの係数も少し部長が手を加えているらしく，そのあたりでバージョンによって違いが出ているわけですが，ツッコミ入れるのを忘れてました。。。

前にジブリ作品「千と千尋の神隠し」の DVD が「赤い！」と騒がれた事がありましたが，今回は見事にその逆を行く形になっています。世間ではディスプレイの「色温度」が云々，なんだか難しそうな話をしていますが，意外にこれと同じミスなんじゃないかな，とか思ってみたりして。

久しぶりに面白いコードを見つけました。JPEG や MPEG は YCrCb 画像から RGB 画像へ ( エンコード時にはその逆 ) を行う時に 0〜255 の飽和演算を行う必要があります。

static inline int _saturation(int in) {
  return (in < 0) ? 0 : (in > 255) : 255 : in;
}

条件分岐を 2 回行いますが，これを 1 回に減らす技がこう。ただしこの技が使えるのは int = 32 bit 環境のみなんですが。。。

static inline int _saturation(int in) {
  return (in & 0xffffff00) ? (in >> 24) ^ 0xff : in;
}

引数に与えられた整数を 0 〜 255 に切り詰めます。サポートしている範囲は -16777216 〜 16777215 だけど，YCrCb -> RGB 変換ではこれで充分。

また YCrCb <-> RGB 変換は主に次のような式で表され，

Y  =  0.2990 * R + 0.5870 * G + 0.1140 * B;
Cr = -0.1678 * R - 0.3313 * G + 0.5000 * B + 128;
Cb =  0.5000 * R - 0.4187 * G - 0.0813 * B + 128;

R = Y                        + 1.40200 * (Cr - 128);
G = Y - 0.34414 * (Cb - 128) - 0.71414 * (Cr - 128);
B = Y + 1.77200 * (Cb - 128);

小数の係数はウザいので，係数をそれぞれあらかじめ 256 倍してたりします。

Y'  =  77 * R + 150 * G +  29 * B;
Cr' = -43 * R -  85 * G + 128 * B + 32768;
Cb' = 128 * R - 107 * G -  21 * B + 32768;
Y  = Y'  / 256;
Cr = Cr' / 256;
Cb = Cb' / 256;
※そういえば，ここで ( Y はもちろん ) Cr や Cb が
　マイナスになることはないっすね。。。

R' = Y * 256                    + 359 * (Cr - 128);
G' = Y * 256 -  88 * (Cb - 128) - 183 * (Cr - 128);
B' = Y * 256 + 454 * (Cb - 128);
R = R' / 256;
G = G' / 256;
B = B' / 256;

この 「 / 256」も飽和演算関数 _saturation() でいっぺんに行ってみると，こう：

static inline int _saturation(int in) {
  return (in & 0xffff0000) ? (in >> 24) ^ 0xff : in >> 8;
}

違いはごくわずかなんだけど，小さいながら強力でもあります。

JPEG が完全に止まってしまったので，気分転換に HTTP プロクシを作ってたりします。意外にサクサク進むので自分でも仰天。

そこで発見。Mozilla は私のプロクシにこんなリクエストを出力してきます。

GET http://www.mozilla.org/ HTTP/1.1
Host: www.mozilla.org
User-Agent: Mozilla/5.0 (Windows; U; Win 9x 4.90; en-US; rv:1.3b) Gecko/20030209
Accept: text/xml,application/xml,application/xhtml+xml,text/html;q=0.9,text/plain;q=0.8,video/x-mng,image/png,image/jpeg,image/gif;q=0.2,*/*;q=0.1
Accept-Language: ja,en-us;q=0.7,en;q=0.3
Accept-Encoding: gzip,deflate,compress;q=0.9
Accept-Charset: ISO-8859-1,utf-8;q=0.7,*;q=0.7
Keep-Alive: 300
Proxy-Connection: keep-alive

私のプロクシは行末の LF まで読み込み，ヘッダをチェックしてから逐次サーバへ流しています。

GET http://〜

OK. サーバに送ります。

Host: 〜

これも OK. サーバに送っちゃいますよ？

User-Agent: 〜

これも行ってよし。

・・・

Keep-Alive: 〜

んー，よく分かんないんで送っちゃえ。

Proxy-Connection: keep-alive

・・・えっ！？

そんな，Keep-Alive 送った後で Proxy-Connection: keep-alive ( Keep-Alive は送るな ) とか言われてもなあ・・・。つまりあれだ，Connection ヘッダや Proxy-Connection ヘッダもある事だし，「受け取りながら送る」って事はやっちゃいけないんですね。一度全てのヘッダを蓄えておき，プロクシ自身がサーバにリクエストし直すという気持ちが必要。プロクシの作り方についてはなかなか文献も少なめなので苦労します。

JPEG ネタは完全に停止しています。やっと 1.3b がリリースされたのはいいけど，なかなか buggy な模様。

-> 3 つも起動してる Mozilla の図 ( PNG 1024x768，24bit )；

画面右下に赤いアイコンが 3 つ。これ全部 Mozilla です。Mozilla が落ちちゃったりすると，アイコンだけ残るんですよね。

んー，実は Nightly という罠。でも，みんなが言うよりは安定しています。WinMe をも黙らせる "k|m マジック" が効いてますか。

かねてからデコードを試みていた MPEG ですが，ついに I ピクチャの画像が見えました！ やった！ 今日はもうこの雰囲気のまま布団かぶって寝たい！ ぜひワッシワッシ眠ってゆきたい！

キモなのは次の部分。会社での作業なのでソースを公開するわけにはいきませんが，コピペではない仮想コードならいいよねえ？

int run, level;

// END OF BLOCK が検出されるまで AC 係数をデコード
while (decode_AC_coeff( &run, &level ) != END_OF_BLOCK) {

  // run 個のゼロを格納する
  while (run-- > 0) {
    coeff[zigzag[z++]] = 0;

    if (z >= 64)
      throw OutOfBoundsException();
  }

  // level を格納
  coeff[zigzag[z++]] = level;

  // もうブロックの終わり -- ループを抜ける   ！これは間違い！
  if (z == 64)
    break;
}

// END OF BLOCK 後は最後までゼロで埋める
while (z < 64)
  coeff[zigzag[z++]] = 0;

8x8 ブロックの AC 係数をデコードする部分で，上のようなコードを書いていました。間違いなのは「！これは間違い！」の部分。ここでループを抜けるのはダメで，ちゃんとこの直後の END OF BLOCK をデコードしてやらなければなりません。

しかしここを間違えて正常なピクチャが取得できなくても，なぜか後のマクロブロックにはほとんど影響を与えないので MPEG の拡張ハフマンコードは萌え要素。感服致しました。

残された問題というと，ハフマン木の作り方を間違えているとか？ だとしたら全く分かりませんっていうかそのセンが濃厚なんですがどうしよう。。。

この JPEG ネタはいつまで続くのやら？

そだそだ，前回のコードにはより単純なバグがありました。これを修正しなければなりません。・・しかし肝心のバグは未だ不明なんですが。。。

次のコードは，逆量子化を行う dequantize() メソッドです。

void JPEGDecoder::dequantize( short *coeff, int cid ) {
  int i=64;
  short *quant_table = quant_tables_[ (cid != 0) ? 1 : 0];
  while (i--)
    coeff[i] *= quant_table[i];
}

cid は「コンポーネント ID」と呼んでいるやつで，輝度成分のデコード中なら 0 を，それ以外 ( 色差成分 ) なら 1 や 2 を保持しています。量子化テーブルは DQT セグメントでいくつか取得されますが，このコードでは輝度成分のデコード中には "0 番目" のテーブルを，それ以外では "1 番目" のテーブルを使おうと企んでいます。

むちゃくちゃです。

cid によって参照すべきテーブルが分かれるのは正解ですが，正確には SOF0 セグメントで取得できる「量子化テーブルセレクタ」を参照すべき。具体的には JPEGDecoder::segment_startOfFrame0() メソッドの中で取得している qt_selector_[cid] ですね。こんな感じ。

void JPEGDecoder::dequantize( short *coeff, int cid ) {
  int i=64;
  short *quant_table = quant_tables_[ qt_selector_[cid] ];
  while (i--)
    coeff[i] *= quant_table[i];
}

これで画質も向上するかなーと思ったら，実はあまり変化はないという罠。人間の目って本当にいい加減なんですねー。。。

今まで考えていたのは「画像の端では実際の MCU の大きさは変化する」というものでした。

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

という条件では通常 MCU には Y 成分が 4 ブロック存在します。しかし 8x8 ドットの JPEG は 8x8 の MCU を仮定すれば充分なわけで，Y 成分も 1 つだけ必要。実際に常識的な JPEG デコーダは，サンプリングファクタが上記のようでありながら Y，Cb，Cr とも 1 ブロックずつしかエンコードされていないデータを正常にデコードします。

しかしながら実際にはそんなフレキシブルな処理は必要ないわけで。なんかこのあたりで悩んでた自分のマヌケっぷりがあっはっは。

前は "何かがなんとなくデコードできたっぽかった" だけなんですが，まぁその実際はほとんど何もデコードしておらず，よく分かんないビットストリームをすっ飛ばしていました。

今日は，ついに何かの形が見えました。おそらく逆量子化がうまくいっていないらしく，見様によってはグチャグチャなブロックの塊？ しかし明らかに目的の画像を形作っています。

ok. 今日も記念日です。

プロジーのDivXコンバータにGPL違反の疑い

さて今私が一生懸命とりくんでいる「オリジナルコーデックによる動画符号化」ですが，どうしてもオリジナルにできない部分があります。すなわち「離散コサイン変換」にまつわる部分。ケンブリッジ大学や MIT にいるような人間ならば日々の暇にちょっと研究するだけで完全に独自のアルゴリズムを編み出すのでしょうが，残念ながら私はそのような脳みそを持っていないようです。っていうか持っているなら半年間もタダ働きしてません。

私が勤めている会社の名前が /. に載るのはいつかなあっ。無茶な仕事を貰ってきた会社と，平凡な頭しか持たない私，悪いのはどっちよ？(泪)

サンプリングファクタの解釈なんだけど，やはり誤解があった模様。MCU が 16x16 である場合でも，画像の右端や下端などで 2，3 ドットしか余ってない場合，例えば 8x16 ドットのように中途半端な MCU としてデコードしなければならないんだ，と考えていましたが，それこそが間違いだった模様。

今日はすっかりこの事にハマってしまい時間が下がってしまったので，詳細はまた明日。

昨日は腕が痛かったんですよ。しかし今日は昨日に比べて幾分よくなって普通の筋肉痛程度。その代わりポンポン痛くなりました。あと微妙に吐き気も。これでは会社に行けません。。。

何かをして気でも紛らわせようと考え，ふと目にとまったのはちょっと前にやりかけていた「スレッドセーフ，タイムアウト付き gethostbyname()」を実現するコード。仕上げて外を見るとすっかり暗くなっていて，腹痛も若干収まりぎみ。明日は会社に行けるかも知れません。

そこでちょっとだけ発見。正露丸の香りを嗅いだだけで，なんとなく助かった気分になります。なぜなんだろう。

・・・夜，再発しました。

※ ソースコードはあとでアプする予定

プライバシー保護という事で詳細はともかく ( 別にスキャンダラスな事でもないけど ) お引越ししました。まさか今日一日で全ての荷物を運ぶとは思いませんでした。というか常識的にあり得ません。おかげで筋肉の繊維は所々破壊されるし，乳酸は溜まるし，イイ事なっしんぐ。すでに筋肉痛が始まっております。

JPEG の問題も全然解決しないしなー。・・・今年が始まって早 1 ヶ月，この雑記でよいニュースを書いた記憶に乏しいんですがいかがなものか。

そっか，もし全世界のマシンに SQL Server がインスコされていたら今ごろ私はこんな雑記を悠長に書いていられなくなっていたわけで。あれだ，ソフトウェアは世界を圧巻するべきじゃないっすね。。。

実は“あっちゃいけない，恥ずかしい”バグがあったので 2003-01-31 にアップしたコードをこっそりとアップし直してみるテスト。・・ぜんぜん“こっそり”じゃないし＞自分

で，これまでにも散々「問題」を抱えては解決して来ましたが，今回のはなかなか厄介です。ちなみに，画像の ( MCU の高さ x 画像の横幅 ) の単位を「行」と呼ぶ事にします。私の JPEGDecoder クラスの getLine() メソッドは，`MCU の高さ' 回呼び出される度に画像を 1 行だけデコードし，内部で大切に保持しています。

まずこれはサンプリングファクタの解釈の問題なのかなと思っていたけど，私のサンプリングファクタの解釈には問題ありませんでした。現在の主な問題はこう：突然，ハフマン符号のデコードに異常を起こします。ハフマン符号をデコードできなかったり，デコードしていたら係数の数が 64 個を超えてしまいそうになったりね。また画像によっては n 行までは上手くデコードできたのに，n + 1 行目の最初の MCU がなぜかスキップされていたり，途中から最後まで何もデコードしていないように見えながら，しかしビットストリームの読み込みだけは無事に終えたりします。要するにつかみどころのない不具合だらけ。

「ステップ実行」で一歩一歩進んでみたり，JPEG バイナリとハフマン符号表 ( DHT セグメントで取得されたもの ) を突き合わせたりしていますが，どうも正常にデコードできるようにしか見えません。一体内部で何が起きているんだろう？

悩んでいる間に休日が終わってしまいました。とほほ。

昨日アップしたコードは，サンプリングファクタがすべて 1 でなければ正常にデコードできません。現在，例えばサンプリングファクタが次のようだったとすると

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

ビットストリームには次の順番で 8x8 ブロックが格納されてあると仮定しています：

• Y ブロック 左上
• Y ブロック 右上
• Y ブロック 左下
• Y ブロック 右下
• Cb ブロック
• Cr ブロック

まさかとは思うんですが，この仮定が間違ってたり？ MPEG では確かにこれで正解ですが，JPEG の場合は確たるリソースをまだ見つけてはいません。ソースコードはあるんだけど，まだ読みこなせていないのです。とほほ・・？