W.Deeの2003年6月の日記

kikyou.info»日記

誠に勝手ながら、kikyou.infoは2017年12月いっぱいをもって閉鎖します。ながらくありがとうございました。

最新月 : 2008年10月
2003年 [             3    4    5    6    7    8    9   10   11   12  ] 月
2004年 [   1    2    3    4    5    6    7    8    9   10   11   12  ] 月
2005年 [   1    2    3    4    5    6    7    8    9   10   11   12  ] 月
2006年 [   1    2    3    4    5    6    7    8    9   10   11   12  ] 月
2007年 [   1    2    3    4    5    6    7    8    9   10   11   12  ] 月
2008年 [   1    2    3    4    5    6    7    8    9   10   11   12  ] 月
2009年 [   1    2    3    4    5    6    7    8    9   10   11       ] 月
前月の日記  次月の日記

2003年6月26日

エイプリルフールだったアレ

4/1 にこのサイトでちょっとふざけたことをやって「ブラクラ」などと言われましたが、また見たい方は以下のリンクをどうぞ (JavaScriptが必要)。 日記システム更新により機能が削除されましたセッションの終わりまでのクッキーを喰わせますのでブラウザを立ち上げ直すと元に戻ります。

文字ごとに文字形状データを取得して ■ 文字でそのドットを表していました。鬼のようにページサイズが大きくなるのですが、圧縮するとぺちゃんこになるので、(可能であれば) gzip 圧縮でブラウザに送りつけるようになっています。

2003年6月23日

vorbisデコーダ最適化

最適化の話題を一つ。

vorbis のデコード処理中にチャネルカップリング(lossless stereoって呼ばれてたやつでしたっけ?)を解除する部分があって、以下のようなコードが書いてあります。

float mag=pcmM[j];
float ang=pcmA[j];

if(mag>0)
    if(ang>0){
     pcmM[j]=mag;
     pcmA[j]=mag-ang;
    }else{
     pcmM[j]=mag+ang;
     pcmA[j]=mag;
    }
else
    if(ang>0){
     pcmM[j]=mag;
     pcmA[j]=mag+ang;
    }else{
     pcmM[j]=mag-ang;
     pcmA[j]=mag;
    }

いろいろと速度的にこのコードは問題があります。

まず、このままだと FPU に正負の判断 (0との比較) をやらせてしまうようなコードを吐くことです。もともと x86 の歴史的に FPU が CPU と別だったせいか、FPU と CPU のレジスタの連携が悪くて、FPU に数値の比較をやらせるとちょっと長いコードを吐きます。

それと、分岐が多いことです。正負の判断後、分岐をさせていますが、とりあえず演算中に分岐があることは、近代的なプロセッサにおいてはかなり速度的に不利です。もちろん 分岐予測が成功しやすいような用途で使われるならばよいですが、この例のように コロコロと条件がかわって、予測がしづらい物の場合は大きなペナルティになります。

で、正負の判断ですが、float の数値表現構造を利用すれば簡単に出来ます。float は 32bit の数値ですが、最上位ビットが 0 ならば正で、1 ならば負なのです。float の数値を整数と見なし、最上位ビットを見て判断すれば FPU に正負の判断をさせる必要はありません。mag = 0 や ang = 0 の場合は今回はあまり考慮しなくて良いですね。

それに、正負を逆にしたければ最上位ビットに xor 1 をすれば良いですし、絶対値をとりたい場合は最上位ビットを倒せばよいことになります。

とりあえず、mag つまり pcmM[j] と ang つまり pcmA[j] を整数でアクセスできるようにします。

long mag = *(long*)(pcmM + j);
long ang = *(long*)(pcmA + j);

 mag+ang とか mag-ang というのがいくつかあります。この ang の正負、よく見ると以下の規則があります。

magang結果

つまり magの正負とang の正負が一致すれば負になっています。

mag の正負は mag & 0x80000000 で、ang の正負は ang & 0x80000000 ですので、(mag & 0x80000000) ^ (ang & 0x80000000)、まとめて (( mag ^ ang ) & 0x80000000) が ビットがたてば ang は 正ということになります。

ang の正負をこれにしたがって逆転したければ、ang にこれをまた xor すればよいことになります。xor 後の ang を temp という変数に作ってみます。

long mag = *(long*)(pcmM + j);
long ang = *(long*)(pcmA + j);

ただ、これだと ang は期待したのとは正負が逆ですが、それは 足し算と引き算を逆にすればよいわけで。mag+ang や mag-ang は、上記の temp を使えば、pcmM[j] - *(float*)&temp で表すことが出来ました。

さて、pcmM[j] と pcmA[j] に結果を代入しているところを見ると、ang の正負によって格納先が違うことが分かります。

ang が負 → pcmM[j] に mag-ang または mag+ang で、  pcmA[j] に mag
ang が正 → pcmA[j] に mag-ang または mag+ang で、  pcmM[j] に mag

これを書くとこうなります。

((float*) (ang & 0x80000000 ? pcmM : pcmA))[j] = pcmM[j] - *(float*)&temp;
((long *) (ang & 0x80000000 ? pcmA : pcmM))[j] = mag;

ですが、?: 演算子は分岐を伴ってしまいます。この程度の ?: 演算だったらコンパイラが論理演算に勝手に置き換えてくれれば良いのですが・・・。

で、どうするかというと、まず ang の正負をマスクにします。ang >> 31 とすると、ang は符号付き整数なので算術右シフトが行われますから、最上位ビットがすべてのビットに移ります (long が 32bit で、負の数に対する右シフトがそういう動作をする前提が必要)。つまり、ang が負の場合に全ビットが 1、ang が正の場合に全ビットが 0 になります。

そこに pcmM と pcmA のアドレスの xor をぶっこんだものと and 演算をします。これを temp2 とします。

temp2 = (ang >> 31) & ((long)pcmM ^ (long)pcmA);

この temp2、ang が負ならば ((long)pcmM ^ (long)pcmA) の値、ang が正ならば 0 になります。

((long)pcmM ^ (long)pcmA) は、(long)pcmM との xor をとれば pcmA が出てくる性質があります。逆に (long)pcmA との xor ならば pcmM ですね。

0 は、pcmA との xor では pcmA そのもの、pcmM との xor では pcmM そのものになります。これらの性質を利用すれば、こう書けます。

((float*)(temp2 ^ (long)pcmA))[j] = pcmM[j] - *(float*)&temp;
((long *)(temp2 ^ (long)pcmM))[j] = mag;

これでとりあえず完成です。全体像は以下のようになります。float を long で読んだりアドレスを long にぶっこんだり、なかなかあぶないコードです。まじめにやるならば、さらに、long が float やアドレス表現と同じサイズであることを assert したりする必要があると思います。

long temp;
register long temp2;
long mag = *(long*)(pcmM + j);
long ang = *(long*)(pcmA + j);
temp = ang ^ ((  mag ^ ang ) & 0x80000000);
temp2 = (ang >> 31) & ((long)pcmM ^ (long)pcmA);
((float*)(temp2 ^ (long)pcmA))[j] = pcmM[j] - *(float*)&temp;
((long *)(temp2 ^ (long)pcmM))[j] = mag;

で、どう速くなったかというと、4860ms かかっていたデコードが 4656ms になりました!

…あんまり速くなってない気もしますが、そんなもんですね。このロジックでアセンブラでかきなおして 4597ms になっています。SSE や 3DNow! の場合も似たようなことをやっています。

wuvorbisfile

吉里吉里用プラグインである wuvorbis.dll を他のアプリケーションからも利用できるようにするためのライブラリを吉里吉里ダウンロードページの方で公開しました。

SSE にくわえて 3DNow! 向けのコードも追加したので結構使い物になると思います。非 SSE 非 3DNow! な CPU でも普通にビルドしたやつよりは速いですたぶん。

2003年6月13日

wuvorbis.dll

久しぶりに CVS から libvorbis (Vorbis エンコード・デコードのリファレンスライブラリ) をひろってきて wuvorbis.dll (吉里吉里用のOgg Vorbisプラグイン) を更新しようかと思ったらいろいろと変わっているようで。

前につくっておいた SSE パッチもまともに動かなくなったので、コードを見直しました。オーバーラッピングと同時に窓関数を適用するようになったのね。

で、新しく wuvorbis.dll を作ったのですが、次のベータ版までは時間が空きそうなので wuvorbis.dll の新しいのをここにおいておきます (最新の物については最新の吉里吉里 SDK ベータ版を参照してください最新版は吉里吉里ダウンロードページの副産物においてあります)。パッチそれ自体は次のベータ版のソース配布に含めます (ただし、VC++ 6.0 用の上、使い方がやや面倒)。

前の最適化パッチは、SSE の movaps ではなくて movups を多用していたのですが、データの配置をよく見直して、使えるところではすべて movaps を使うようにしました。これだけで結構速度が違う模様。

最適化パッチ後は、非最適化パッチ適用時の約 1.46 倍の速度でデコードできます (もちろん条件にもよりますが)。前の最適化パッチが 非最適化時の 1.34 倍だったかだから、とりあえず速くなったってことです。

2003年6月5日

MD5

MD5 生成ライブラリを探してこのサイトにいらっしゃる方が結構いらっしゃるんですが、自分は「Independent implementation of MD5」というのを使っています。これの一時配布元を探そうとしましたがなかなか見つかりません。Google で「Independent implementation of MD5」を検索するとソースそのものは入手できます。

ライセンス的にも使いやすいのでお勧めです。