HOME | PRODUCT | BBS | CODE
Code | Memorial | Sample | Reference
List | -10 | -20 | -30 | -40 | -Latest
since 2000/10/01
#1 (2000/02/21 )
　反転
#2 (2000/02/23 )
　8bitマスク生成
#3 (2000/02/24 )
　8bitマスク生成 その2
#4 (2000/02/25 )
　8bitマスク生成 その3
#5 (2000/02/25 )
　速報：テーブルは遅い!!
#6 (2000/02/27 )
　やっぱりテーブルは遅い!!
#7 (2000/03/01 )
　反転マスクの生成法
#8 (2000/03/01 )
　飽和加算のために その1
#9 (2000/03/04 )
　8bitマスク生成 その4
#10 (2000/03/05 )
　sin/cosに苦しむ

Tip Mark
欄外情報FOOTNOTE　 参考リンクLINK　 補足事項NOTICE
sanami@aya.or.jp

第1回 ： 反転
さて、仄香セイバーなのです。 なにかっちゅーと、反転コードは仄香セイバーで考えに考えたのです。 で、結論から言うと、つい先日思いついたコードが最も速いということに気がついたりしてしまって、 現在の仄香セイバーはあんまり速くないわけですよ。 だからといっても、すでに完結したプロジェクトなんでパッチを作成する気はないんですけどね。

それはともかく、ぎゃるぱにＸを作成する際に、 DirectDraw関係の情報を求めてインターネットをさまよっていたのですが、 なにかって〜とDirect3Dをすすめるのはなんなんでしょうね。 回転がやりたいって質問があると決まってDirect3Dを使ってどうたらこうたらって、 う〜む。Direct3Dを否定する気はないんですけど、 3Dボード以外を考えるとなんでもかんでもDirect3Dってのは・・・。

愚痴はおいといて、本題に入りましょう。反転なのです。
たかだか反転パターンを使うのにDirect3Dは使わんでしょうということで、 ソフトウェアで反転するわけです。それにしても、 反転ぐらいハードウェア側で実装して欲しいと思うのは僕だけですかね。

一番簡単なコードってのは，一番最初に誰しもが考えるコードで， C言語でかけば

src = src +4;
for(i = 0; i < 4; i ++)
    *dst++ = *src--;
ってな感じです。 こいつを展開したとすれば 
mov [dst], [src]
inc dst
dec src
mov [dst], [src]
inc dst
dec src
mov [dst], [src]
inc dst
dec src
mov [dst], [src]
inc dst
dec src
こんな感じでしょうか。decは結果をフラグレジスタに書きこむ命令っぽいので、 例外的にmovとペアリングできそうです。 ということは、6クロックで4byteの反転ができそうです。 こいつを高速化しましょう。

で、よくある考えかたはDWORDで処理するってことで、4Byteずつどうにかするわけです。 そもそもなんで反転かっつーと、BSWAPという便利な命令があるからなんです。 この命令、レジスタのエンディアンを変更するんですが、 結果としてbyte単位で左右反転していることに等しいんです。 さて、この命令を使えば

mov   eax,[src]
add   src,4
bswap eax
mov   [dst],eax
sub   dst,4
ってとこですか。最初の2命令がペアリングできそうです。 そのかわりbswapがプリフィックス命令でデコードに時間がかかるため、 1+2+1+1=5クロックでしょうか。 少しは速くなったかもしれません(^^;

どうもbswapが鬼門のようです。 ちゃんと調べるまでは便利な命令だと思ってたんですが、 あんまり使えないんでしょうかね。ループを工夫して、 

mov   eax,[src]
sub   dst,4
bswap eax
mov   [dst],eax
add   src,4
のようになるようにすれば 1+2+1=4クロックになりそうな気もします。
まだまだ考える余地がありそうです。
Virtual Payment System100えん10えん1えんヘルプ

第2回 ： 8bitマスク生成
8bitマスク生成なんです。何に使うかっていうと、 256色のスプライトを合成するために使うんです。 そんなのハードウェアアクセラレーションを使えばいいと思ったあなた、正解です。 でも、仄香セイバーは全部自前なんです。確か、Win32APIのSetDIBitsToDeviceには色抜き転送なんてないはずです。 たかがスクリーンセイバーでDirectXを使うこともないし、 そもそもどんなロースペックなマシンでも動くことを目的にしているんで、 自前しかないんです。多分。

普通に考えれば、index = 0 の色を透過として、 

if(a==0)
 a = b;
でいいはずです。 でも、これだと分岐命令があるので遅そうです。 これをどうにかしましょう。

ただ単に上のコードを分岐無しにするには、 

CMP EAX,1
SBB EAX,EAX
XOR ECX,EBX
AND EAX,ECX
XOR EAX,EBX
http://www.csl.sony.co.jp/person/fnami/pentopt.htm
が使えますが、これでは分岐無しにした意味さえなくなるほどの量です。 せめて DWORD 単位でしたいところです。

ところで、スプライト転送を考えた場合、これは

という二つの問題に分かれます。 命令のペアリングを行うより前に、この二つのステージにわけて考えると問題が簡単になります。 さて、まず index = 0 の判定です。今、DWORD で処理しているとすれば 
AND EAX, 0x000000FF
で最下位 byte の 0 判定ができます。が、これを4回繰り返すのは…ちょっとやですね。 なんとか4byte 分１度にやってしまいたいところです。

僕が次に考えたのは、畳み込みです。 まず、4bit シフトして OR をとります。これで 8bit の判定が 4bit の判定でよくなります。 次は・・・言うまでもなく、これを 1bit まで繰り返せばいいですね。 ところが、これ、結構長くなるんです。 

MOV EBX, EAX
SHR EBX, 4
OR  EAX, EBX
SHR EBX, 2
OR  EAX, EBX
SHR EBX, 1
OR  EAX, EBX
AND EAX, 0x01010101
わりとよさげですが、ちと長いです。ペアリングを考えると、 SHR EBX, n で EBX に書きこんでますから SHR-OR ではペアにできません。 逆に OR-SHR では SHR が V パイプで実行できないのでペアにできないんです。 もしペアにできれば速いんですけどねぇ。残念。 さて、結論。桁上がりを使いましょう。 8bit 値を考えたとき、0xFF 加えると 0 以外のときはすべて桁上がりがおこります。 ここで重要なのは、足し算なので桁上がりは 1 なのです。8bit 値 + 0xFF は 0x0FF〜0x1FE の範囲におさまります。 と、いうことは桁上がりの 1bit で 8bit 値の 0 かどうかの判定ができることになります。 これが基本的な考えです。

桁上がりを使って 0 の判定をするのはいいとして、 4byte 同時にするにはどうしましょう。ただ単に 0xFFFFFFFF を加えたらそれはひどいことになりますね。 これは下位 byte の加算の桁上がりが上位 byte に影響するのが原因です。 ということは、こいつをどうにかすればいいだけの話です。 桁上がりを無いようにするのは、実に簡単です。8bit 全部使うからあふれるのであって、 8bit のうち、7bit しか使わなければ絶対に桁あふれはおきません。 ということですから 

AND EAX, 0x7F7F7F7F
ADD EAX, 0x7F7F7F7F
とすればいいわけです。となると最上位の 1bit を忘れちゃいけませんから 
MOV EBX, EAX
AND EAX, 0x7F7F7F7F
ADD EAX, 0x7F7F7F7F
AND EBX, 0x80808080
OR  EAX, EBX
ですね。これで各 byte の最上位 bit が 0 なら、その byte は index = 0 であることになります。 ・・・が、ここで AND EBX, 0x80808080 は意味が無いですね。次の命令で OR とるんですから。 OR の相手の EAX の各 byte の下位 7bit は何が入ってるかわからない（＝情報として無意味）のです。 ということで、最後に無意味な情報は消しときましょう。 
MOV EBX, EAX
AND EAX, 0x7F7F7F7F
ADD EAX, 0x7F7F7F7F
OR  EAX, EBX
AND EAX, 0x80808080

なんか、長くなってきたので今日はここまで。次回にマスクを作ります〜。

Virtual Payment System100えん10えん1えんヘルプ

第3回 ： 8bitマスク生成 その2
いやいや、まったくもっていやはや。自分で書いたコードを読み解くのはつらいもんです。 書いたときは素晴らしいコードだと思って掲示板に書きこんでおいて、 後日、ほかの人に説明しようと思ってコードを見なおしたら・・・、 う〜む、わからん。しかも、なんか間違ってる気が・・・だめじゃん。 ということで、ここで説明しとくと未来の自分が読みなおしてウハウハ（え？。

さて、マスクを作ります。材料は 1bit のフラグデータです。 フツーに作ろうと考えれば、 1bit のフラグを 8bit になるまでコピーしますね。 フラグデータが EAX:FxxxxxxxFxxxxxxxFxxxxxxxFxxxxxxx (F:flag bit) となっているとすれば 

MOV EBX, EAX
SHR EBX, 1
OR  EAX, EBX
MOV EBX, EAX
SHR EBX, 2
OR  EAX, EBX
MOV EBX, EAX
SHR EBX, 4
OR  EAX, EBX
で EAX にマスクが作成できます。見てのとおり、遅そうな感じがあふれてます。 で、なんとかもっと簡単に作りましょう。

仄香セイバーでは 0 - (EAX >> 7) + (EAX << 1) として作成しました。 基本となるのは 0 - 1 で FFFFFFFF を作ることです。 これを 4byte 同時に作ることを考えるわけですが、ただ単に引いただけでは見てのとおり、 ほかの byte に影響がでてしまいます。000000FF を作る場合は 0 - 1 ではうまくいかないのです。 ここでよくよく考えてみれば、1 引いた結果、上の桁から 1 を借りてくるために 0 が 1 になるのですから、必要以上に上の桁から 1 を借りてこなければいいのです。 つまり、 00000000 - 1 としたら、上位 byte からは 1 を借りてこないように、 00000100 を足してあげます。これで 00000000 - 1 + 00000100 = 000000FF となり、 目的は達成できました。このコードは次のようになります。 

XOR EBX, EBX
SHR EAX, 7
SUB EBX, EAX
SHL EAX, 8
ADD EBX, EAX
さて、こちらの掲示板を読んでいてハッとしたのですが、
0 - (EAX >> 7) + (EAX << 1) ってことは、
(EAX << 1) - (EAX >> 7) でも同じ結果が得られます。 
MOV EBX, EAX
SHR EAX, 7
SHL EBX, 1
SUB EBX, EAX
1命令減ってますね。

しか〜し、僕はあまりのショックで悔しかったので考えに考えましたですよ。 その結果、さらに素晴らしい（おそらく最速）のコードを思いつきました。 仕組みは次のとおり。 

7F + 01 = 80 -> 80 xor 80 = 00
7F + 00 = 7F -> 7F xor 80 = FF
簡単ですね。これをコードにすれば、 
SHR EAX, 7
ADD EAX, 7F7F7F7F
XOR EAX, 80808080
これでオッケーです。1命令減りました。 u パイプでしか実行できないシフト命令を減らすことができるのはいーんですが、 いかんせん、一つのレジスタに連続でアクセスしなければいけないのがつらいとこです。

ふと気がつきましたが、ここで書いてる内容って、ペアリングまでしないのなら、 言語レベルでも使うことができるんですね〜。おお、お徳。 上のコードだったら、 

unsigned long EAX;
EAX >>= 7;
EAX += 0x7f7f7f7f;
EAX ^= 0x80808080;
ですね。コンパイラの最適化をかければそのままアセンブラにしてくれそうな気もしますし。 横道にそれました。

で、今考えているのは、SHR命令の削減。この命令がなくせるとペアリングが楽になるんですよね。 方法としては、

の二つですが、何をいってるかわかりませんね(爆)。 いーんです、覚え書きなんで。

そんなこんなで、 スプライト表示のためにマスクを使って二つのデータを合成するのですが、 この合成部分でもさらなる苦労ができるのでそれは次回で。 ああ、ネタがあるって素晴らしい・・・。

Virtual Payment System100えん10えん1えんヘルプ

第4回 ： 8bitマスク生成 その3
さてさて、こんなことをしてる場合じゃないのです。 なにかっつーと、 こんなどうでもいいような最適化の話よりもさらに大きな問題に気がついてしまったのです。 というわけでデータの合成の話は後回しにして、より重要な話を先にしようと思ったのです。 でも、よくよく考えてみれば、合成の話はほんの少しだけしかないので(笑)、 さくっと終わらせてしまって次の話をさくっと書いてしまおうと思ったのです。 ということで、さくっといきます(^^;。 まず、マスクを使ってデータを合成する場合をすなおに書くとしましょう。 EAX と EBX にデータが入っていて、ECX にマスクが入っているとします。 
AND  EAX, ECX
NOT  ECX
AND  EBX, ECX
OR   EAX, EBX
これで合成は完了です。 さて、こちらの掲示板の小次郎さんがあげていられて気が付いたのですが、 a xor a xor b = b になります。これを利用すると、 
XOR  EBX, EAX
AND  EBX, ECX
XOR  EAX, EBX
こうなります。これは、 
マスク FF -> EAX = (EAX xor (EAX xor EBX))
マスク 00 -> EAX = (EAX xor 00)
という原理を使っているわけです。 これで合成も1命令減で、全部の話が終わりました。 今までのコードをまとめると、EAX にスプライトデータ、EDX に背景データが入ってるとして 
MOV  EBX, EAX
AND  EAX, 7F7F7F7F
ADD  EAX, 7F7F7F7F
OR   EAX, EBX
AND  EAX, 80808080
SHR  EAX, 7
ADD  EAX, 7F7F7F7F
XOR  EAX, 80808080
XOR  EBX, EDX
AND  EBX, EAX
XOR  EDX, EBX
となります。このコード、見てのとおり EAX にアクセスが集中しててペアリングが全く出来ません。 ということで僕自身あんまりいいコードじゃないのかなぁ、と思ってましたが・・・ 実はやっぱりすごいコードかも知れないです、ホント。こんだけ EAX しかアクセスしないってことは、 逆に言えば、EAX しか重要じゃないってことです。と言うことは・・・気が付きましたか？ ループを展開できる可能性が高いってことです。つまり、上のコードでは 4byte を同時に処理するわけですが、 8byte の処理を考えたときに上のコードを２回繰り返すのではなく、 ペアリングして同時実行することができるということです。これは速いはず、ですね。

ところで、今まで役に立たないかと思っていたコードがループを展開するときに使えそうです。 

SHR EAX, 7
ADD EAX, 7F7F7F7F
XOR EAX, 80808080
マスクフラグからマスクを生成する部分です。これって、順序を入れ替えることができます。 
ADD EAX, BFBFBF80
SAR EAX, 7
XOR EAX, 00808080
もしくは 
ADD EAX, BFBFBF80
XOR EAX, 40404000
SAR EAX, 7
ここで気をつけなければいけないのは、ADD で加える値は 7F7F7F7F <<7 になることと、 最後の XOR で反転する必要のある bit の場所ですね。 SAR は算術シフトで左に空いた bit を、今までの最上位 bit と同じにするようにするシフトです。 したがって、最上位 bit が1のときは 7bit シフトすると 11111111xxxxxx... となりますから、 最上位だけは XOR で反転する必要はないということになります。 そのため、XOR 00808080 ということになるわけですね。

さて、なんで順番が入れ替えられるとループを展開するときに使えるのでしょう。 答は簡単、u パイプでしか実行できないシフト命令を移動できるからです。 ただ単に 4byte 2セットを並列処理することを考えると、 当然のことながらシフト命令も同時に実行することになるわけです。 しかし、シフト命令は u パイプでしか実行できないのでペアリングできないということになります。 もちろん、並列処理の順序をずらすということでも解決できますが、 シフトのタイミングをずらすことができれば、さらに自由度も高くなりますから、 ペアリングの可能性も増すってことです。 ま、実際に使うかどうかは別の問題ってことで。 ちょっと試してみようとしてますが、時間がかかりそうなので先に次の話題を(^^;。 さらっと、といったワリにはいろいろあって長くなりましたね〜。 そんなこんなで、次が今日のメインです(笑)

Virtual Payment System100えん10えん1えんヘルプ

第5回 ： 速報：テーブルは遅い!!
テーブルは遅いんです、という話なんです。 今まで、メガデモなんかの話では散々聞かされた「テーブルで高速化」は一部ウソでした(^^;。 ということなんで、テーブルを使ったメガデモは今後メガデモと呼んではいけません（え？。 で、これからはテーブルを使わないデモを「さ〜デモ」と呼ぶことを主張します(笑)。

話の発端は、15bitαブレンディングでした。 よくはわからないので間違っているかもしれませんが、MMXでは8bitごとでのパック演算はできますが、 5bitごとの演算はできないはずです。そこで、MMXを使うなら変換が必要になるから、 ああ、それじゃテーブル使わなきゃやっぱりだめかねぇ、と思いました。 ここで問題となるのがテーブルの大きさで、15bit ってことは 32768 通りありますから、 これに WORD サイズ2byteをかけて64Kbyte必要です。 ところで、このサイズってことはキャッシュにのるの？ということです。 最近のパソコンは L2キャッシュはわりと多くなって、まぁ512Kbyteとかそのあたりまではあるはずです。 でも L1キャッシュはそんなにないはずです。調べてみると、 P54C（ノーマルPentium）と Pen Pro で コード用 8K とデータ用 8K 、 MMX と PentiumII でそれぞれ 16K ということです。ということは、 64KbyteのテーブルはL2キャッシュにのる程度ということです。 さらに、αブレンディングってことは、このテーブルが2つ必要ですから（方式にもよります）、 それを考慮すれば128Kbyteのテーブルが必要です。L2キャッシュの仕組みは知りませんが、 かりに512Kbyteをコード用とデータ用で半々に使ってるとすれば、 この2つのテーブルだけでデータ用キャッシュの半分を占めるので、 これは大きな負担でしょう。

さて、ここではL1キャッシュとL2キャッシュ間の話に絞ることにします。 L1キャッシュにデータがない場合はどれだけ遅れるのでしょうか？ こちらのページによればキャッシュラインをコピーするのに200ns かかるが、 最初のデータは50〜100ns で利用可能になるとあり、200MHzで10〜20クロックに相当するとあります。 ということは、どんなにテーブルが速いといっても、10〜20クロックかかるということです。 なぜなら 128Kbyteのテーブルに（画像処理ですからランダムといっていいはずです）無作為にアクセスするということを考えると、 これに対したかだか16Kbyteのキャッシュではほぼ100%ミスキャッシュになるはずです（おおげさですか？）。 まぁ、逆に100%ということはありませんけど(^^;。90%とかぐらいはいくのではないでしょうか（画像によりますね）。 と、いうことは10〜20クロック以内の命令であれば直接計算したほうが速いという結論になります。 直接計算にはもう一つの利点があります。キャッシュを必要としないので、 テーブル以外のデータのヒット率があがるということです。

という仮定に基づきテストをしてみました。 プログラムはこちら5-tabletest.cpp (1930 bytes)にあります。 15bitデータを考えて、これをフェードアウトするように R:5 G:5 B:5のそれぞれについて 0でなければ 1引くというものです。 データがキャッシュに入る可能性も考えて、1回ダミーで処理した後に100回試行します。 だいたいのプログラムはこんな感じです。 

-----------------------------------------------------------------------
#include "stdio.h"
#include "stdlib.h"
#include "windows.h"

void main(void) {
    DWORD timesrc, timedst;
    WORD *src, *dst;
    src = new WORD[640*480];
    dst = new WORD[640*480];

	// テーブルの作成
    WORD *table;
    table = new WORD[32768];
    for(int i = 0; i < 32768; i ++) {
        WORD w = i;
        w &= 0x3DEF;
        w += 0x3DEF;
        w &= 0x4210;
        w >>= 4;
        w += 0x3DEF;
        w ^= 0x4210;
        w &= 0x4210;
        table[i] = i - w;
    }
    srand(timeGetTime( ));       // 乱数初期化
    // 元イメージ作成
    for(i = 0; i < 640*480; i ++)
        src[i] = rand( ) & 0x7fff;

    //----------------------------------------
    // テーブル使用版
    // 開始
    timesrc = timeGetTime( );
    for(test = 0; test < 100; test ++)
        for(i = 0; i < 640*480; i ++)
            dst[i] = table[src[i]];
    timedst = timeGetTime( );
    printf("table use: %ld\n", timedst - timesrc);

    //----------------------------------------
    // テーブル未使用版
    // 開始
    timesrc = timeGetTime( );
    for(test = 0; test < 100; test ++) {
        for(i = 0; i < 320*480; i ++) {
            DWORD sv = *((DWORD*)&(src[i*2]));
            _asm{
                MOV  EAX, sv
                MOV  EBX, sv
                AND  EAX, 0x3DEF3DEF
                ADD  EAX, 0x3DEF3DEF
                AND  EAX, 0x42104210
                SHR  EAX, 4
                ADD  EAX, 0x3DEF3DEF
                XOR  EAX, 0x42104210
                AND  EAX, 0x04210421
                SUB  EBX, EAX
                MOV  sv, EBX
             }
             *((DWORD*)&(dst[i*2])) = sv;
         }
     }
    timedst = timeGetTime( );
    printf("no table : %ld\n", timedst - timesrc);
 }
-----------------------------------------------------------------------
コンパイルはVisual C++なら cl tabletest.cpp /link winmm.lib として下さい。 プロジェクトを作る場合は設定→リンクでwinmm.lib をリンクして下さい。 で、実行結果。
PentiumII 333MHzMMX Pentium 120MHz
テーブル使用(ms)251515011
テーブル未使用(ms)15314639
いや〜、びっくり。 最初、元イメージデータを 
    for(i = 0; i < 640*480; i ++)
        src[i] = i & 0x7fff;
として作っていて、結果が芳しくないのでおっかし〜な〜と思っていましたが、 よくよく考えたらこのデータじゃ、キャッシュ効きまくりですな(笑)。 それに気づくのに3時間かかりました。でも、最適化をかけなければそれでもテーブル未使用のほうが速かったです。 で、タイトルを「!?」にしてたですよ。原因がわかったので「!!」に戻しましたけど。 一応、言っておくと、上のプログラムをそのまま最適化するとデータの依存関係の解析からだいぶ違うコードになってしまい、 正しい結果が得られないはずなので、 最適化するときはそれぞれのルーチンに対して出力のdstをなんらかの操作に使うようにしてくださいね。 例えば、 
    a ^= dst[i];
みたいな感じです。

いや〜、この話しは我ながらびっくりでした。ちなみに、 sin/cosをテーブルで使うのは問題無いと思いますね。2πを何分割するかにもよりますが、 そんなに多くはしないですよね？いくらなんでも10〜20クロックじゃ計算できんよねぇ、近似値でも。 いや、ちらっと考えましたけど(笑)。その問題については、ほかのことを優先してるんで後回しです(^^;

ああ、疲れた。

Virtual Payment System100えん10えん1えんヘルプ

第6回 ： やっぱりテーブルは遅い!!
メガデモの定石として、仮想画面を1次配列で確保して、その仮想画面の任意の点にアクセスするときに、 乗算を行わなくてすむようにテーブルを使うというのがあります。 
BYTE *img = (BYTE*)malloc(sizeof(BYTE)*640*480);
BYTE *ptr[480];
for(int i = 0; i < 480; i ++)
    ptr[i] = img +i*640;
こんなのですね。このテーブル、実際問題として速いのでしょうか？ サイズ的にはたかだか 480x4=1920 byte ですから問題はありません。 でも、これって連続アクセス以外では能力を発揮できないのではないでしょうか？ というのが今回のお題です。 前回の結果から、ミスキャッシュすることが多い場合は、 10〜20クロック程度の命令で記述したほうが速いことがわかります。 とりあえず、ミスキャッシュするものとしてテーブルを使わないとき、 何命令でかけるか試してみましょう。 EAX に x座標、EBX に y座標、ECX にベースアドレスが入っているとして、 
LEA  EBX, [EBX*4 +EBX]   // EBX = EBX * 5
SHL  EBX, 7              // EBX = EBX * 128
ADD  EAX, ECX
ADD  EAX, EBX
こんなところですね。LEA を使うときは AGIストールに気をつけなければいけないので、 2行目と3行目を入れ替えたほうがよいですか。SHL を先に実行しとくこともできますね。 まぁ、3クロック程度です。ミスキャッシュした場合だったら確実に速いですね。

問題は、ミスキャッシュのときとキャッシュヒットのときの差が使用頻度にあっているか、 です。 かりにミスキャッシュでのアクセスが10クロックかかるとしましょう。 テーブルを始めて参照するときは100%ミスキャッシュですから、 10クロックかかります。以降はヒットするとして1クロックとしましょう。 テーブルを使った場合と使わない場合、速度で逆転するのは何回のアクセスでしょう？。 10+(n-1)=n*3 という式を立てて、n=4.5です。 つまり、テーブルを使う場合は連続して5回以上の参照をして始めて意味があるということです。

ところで、L1キャッシュは 32バイト長のキャッシュラインに分割され、 データはキャッシュラインごとに読みこまれます。 32バイトということは 32/4=8 ですからポインタ 8個分ですね。 したがって、上で求めた連続5回以上の参照はこの範囲でおさまっていることが条件に加わります。 もし、table[0] を参照した後に table[8] を参照すると、 ここで再びミスキャッシュになり 10クロックかかります。 そーゆーことですから、１箇所に集中した参照が見こまれないテーブルは遅いはず、です。

ちなみに、キャッシュラインはアドレスの 5〜10ビットを使って読みこむようで、 5〜10ビットが等しい場合には最大 4つ（P54C/Pro では2つ）のキャッシュラインを保持することができます。 この 5〜10ビットが等しいということは 4096byte周期ということを意味します。 さて、4096byte というと 640x480x16 画像を考えたとき、 4096/2/640=3.2 ですから 3.2ライン分に相当します。 画像処理するために走査していくと 3.2*4=12.8ラインを走査した後はミスキャッシュになります。 このとき、テーブルとも競合するわけですから、テーブルがL1キャッシュから破棄される可能性があることを意味します。 そんなわけですから、よほど限定されていないかぎりポインタテーブルを使うのは・・・。

ここまでは任意の点にアクセスする場合です。 より限定された条件を考えればテーブルの意味はなくなることもありえます。 画像のすべての画素に対して明度を落とすことを考えましょう。 左上から右下に向かってすべての画素を走査します。 そのまま書けば 

for(int y = 0; y < 480; y ++)
    for(int x = 0; x < 640; x ++)
        ptr[y][x] = ptr[y][x] - 1;
のようになります。この場合、8ラインごとにミスキャッシュになるわけですね。 でも、たかがこの程度の走査に対してテーブルが必要なわけがありません。 リニアに 
DWORD *ptr = base;
for(int y = 0; y < 480; y ++) {
    for(int x = 0; x < 640; x ++) {
        *ptr = *ptr -1;
        ptr ++;
     }
 }
でもかまわないはずですし、DirectDrawのsurfaceのようにぶつ切れになっているなら、 
DWORD *ptr = base;
for(int y = 0; y < 480; y ++) {
    for(int x = 0; x < 640; x ++) {
        ptr[x] = ptr[x] - 1;
     }
    ptr += scanline;
 }
とでもできます。この場合なら、更新の手間は ADD 命令だけですからテーブルと変わらんですね。 そんなこんなでやっぱりテーブルは遅いのです。

あ、そうそう、sin/cosを 10クロックで書くのはあきらめました。 テーブル使ってください(笑)。 cosのテイラー展開を使ってみましたが、xの2乗の項までだとπ/4ぐらいまでが限界です。 それ以上は誤差が大きすぎます。 ちなみに、xの4乗まで使えばπ/2で誤差が0.02程度ですから、まぁなんとかいけるかな、 というレベルですが、掛け算が２回必要ですねぇ。掛け算1つで10クロックですから… 意味ないっす。

おまけ
１回分の内容には遠く及ばないので、ここにこそっと書いときます。 データは 32byteにアラインしよう！。そのわけは簡単、 キャッシュラインサイズが32byteだからです。 と思いついたのはよかったけど、 キャッシュについて詳しく読んだら、 書いてありました(笑)。ま、いいか。

それはそうと、キャッシュを考えると実行クロック計測はほぼ不可能な気がしてきた。 だって、初回の実行の計測はキャッシュヒットしてないわけだし。 ロード待ち時に、CPU内部のクロック計測カウンタが止まっててくれれば簡単なんだけどねぇ。

Virtual Payment System100えん10えん1えんヘルプ

第7回 ： 反転マスクの生成法
いろいろ仮定はできても、実証コードがないんじゃアレなんで、 基本に立ち戻ってあんまり熱くない話題でお茶を濁しときます。 だったら更新しなければいいという話もありますが、 それじゃぁ現実逃避にならんじゃないですか(笑)。 そんなこんなでキャッシュ関連の考察はいろいろしてるんですが、 あんまり面白い仮説は得られていないor計測してない、ので、 ちょっとそこから離れてマスク生成についてです。

と、ここまで書いてあったんですが、急に新しいっぽいことを思いついてしまいました(笑)。 そんな感じなんで、またさくっと流してしまいましょう(^^;。

本題です。第4回でフラグからマスクを生成するときに、 (FLAG + 7F) xor 80 で求まることを説明しました。 この場合、FLAG=0のbyteには FF のマスクが、FLAG=1のbyteには 00 のマスクが生成されます。 単純に考えると、得られたマスクの反対のマスクが欲しい場合には、 NOT FLAG とかで得るわけです。

これをちょーっと考えると、そんなことしなくてもいいことがわかります。 (80 - FLAG) xor 80 でいーんです。 

80 - 01 = 7F -> 7F xor 80 = FF
80 - 00 = 80 -> 80 xor 80 = 00
ばっちりですね。 用途によって使い分けましょう。 最適化の道が広がったということで、ま、何かの役に立つかもしれません。 っちゅーか、役に立ってます。(^^;
Virtual Payment System100えん10えん1えんヘルプ

第8回 ： 飽和加算のために その1
ふと思いついたので、最適化に関してはまだまだなので、 思いついた部分だけ記録に残すっつーことで書いときます(^^;。 飽和加算を考えていたんですが、まぁ、わりと面白いかなぁ〜と。 話題の中心は飽和のチェックフラグからマスクを生成した後にあります。 たとえば、8bit x4の値を考えた場合なら、 飽和するbyteは FF に、そうでないbyteは 00 であるようなマスクですね。 このマスクを作った後、実際の足し算をするわけですが、 まぁ普通に考えれば、EAXとEBXにソースデータが、 ECXにマスクがあるとしましょう。 
NOT ECX
AND EAX, ECX
NOT ECX
ADD EAX, EBX
OR  EAX, ECX
とすれば飽和するbyteは FF になりますね。 最初の NOT は上の回を参考にすれば、 反転した状態で生成できますから、ないものとして考えていいです。 ということは、4命令です。

今回思いついた方法は、 

ADD EAX, EBX
SUB EAX, ECX
OR  EAX, ECX
こうです。 いきなり書いてもわけわからんですね。 思考の途中経過を追って説明しましょう。

飽和するっちゅーことは、どーゆーことでしょう？簡単ですね。 一定のbit数で加算をして、オーバーフローしたときにbitすべてを1にすることです （そう決めたのです(^^;）。 1byteの加算ならオーバーフローはキャリーフラグで判定できますが、 複数byteを１度に計算するためには、キャリーフラグなんて使えません。 今のところでは、飽和チェックの結果は各byteの最上位bitの0/1として得られてます。 ってことは、左1bitシフトしたものを引いてあげればオーバーフローによる影響を打ち消すことができます。 EAXとEBXに8bit x4の画像があったとし、OVERがオーバーフローのフラグとします。 

(EAX + EBX) - (OVER << 1)
これで、飽和したbyte以外のbyteに関する演算は終了したことになります。 最後に、OVERから作り出したMASKをorすればすべて終了なのですね。

さてさて、(OVER << 1)っちゅーのがすげー嫌だったんです。 ま、比較的って意味でですが、ペアリングするときにuパイプだけっちゅーのがやりにくい、 てことです。 いろいろ考えていたんですが、わざわざ(OVER << 1)として引く必要がない、 というのが今回の主張です。

何をしたいかというと、上位byteから1引けばいいわけです。 で、飽和したbyteは最後にマスクとorを取るので、どんな値になってもかまいません。 以上のことを踏まえて、ほかにいい方法はないでしょうか？ 答はyesです。飽和したbyteから FF を引いても同じ結果になります。

それが正しいことを説明しましょう。 100〜1FFの値で、FFを引いても100以上になる値は1FFだけです。 これは 100+FF=1FF ですから当然のことです。 ところが、1FFってどこからでてきたのよ、 と考えると、これは二つの1byte値を加算した結果に得られる値であります。 でも、ここでさらに考えてみましょう。何と何を加えたら1FFになりますか？ そうです、片方を1byteの最大値 FF にすると、もう片方の値は100になります。 けど、そんなの1byteの値じゃないですから存在しません。 両方が最大値だったしても FF+FF=1FE です。 したがって、100以上値のとき、 FFを引くと必ず100未満の値になることがわかりました。 これは見方を変えれば、オーバーフローの影響をなくしているということです。

さぁ、都合よく話がすすんできたところで、 じゃぁ、FFをどうしよう、ということですが、あぁ、マスクがあるじゃ〜ん。 で、解決です。 二つの値を何も考えずに足し合わせた後、マスクをそのまま引けば、 オーバーフローによる影響はなくなります。 最後に、飽和したbyteをFFにするべく、マスクとorをとってあげればいいですね。 ということで、 

((img1 + img2) - MASK) or MASK
が得られるわけなんですよ。
Virtual Payment System100えん10えん1えんヘルプ

第9回 ： 8bitマスク生成 その4
ちーす、現実逃避レベルがかなり高くなってます(笑)。 とりあえず、8bitマスクを使用した合成について、 完全ペアリングができたっぽいのでそのレポートです。 という前にうかつ過ぎるミスがあったので。

第4回でマスクを使ってデータを合成する部分を、 EAXにスプライトデータ、EBXに背景に見えるデータ、ECXにマスクデータとして 

AND EAX, ECX
NOT ECX
AND EBX, ECX
OR  EAX, EBX
と書いてました。つい先日気がついたのですが、 実は意味がありませんでした(^^; 
NOT ECX
AND EBX, ECX
OR  EAX, EBX
だけで十分でした。 なぜそうなるかについて、です。 そもそもスプライトデータとマスクデータのANDを取るのは何故でしょうか？ 簡単です。合成するときに、マスク部分以外のデータが邪魔だからです。 そういえば、マスク部分以外って〜と、なんでしたっけ。 ああ、00 じゃないですか(笑)。 あれ？もしかして、AND って実行してもしなくてもおんなじ？ うゎぁ、意味ね〜。以上です。 なんで気づかなかったんだろ・・・＞オレ

さて、NOT ECX ですが、こいつも実はいりません。 マスクデータを作るときに、最初から反転したデータを作成すればいいってことですからね。 それでは全部書きなおしときます。 edxが指しているデータがスプライトデータ、 ebxがスプライトを表示する先のデータを指していると思いこんでください。 

mov eax, [edx]
and eax, 0x7f7f7f7f
add eax, 0x7f7f7f7f
mov esi, [edx]
or  eax, esi
and eax, 0x80808080
shr eax, 7
add eax, 0x7f7f7f7f
xor eax, 0x80808080
mov esi, [ebx]
and eax, esi
mov esi, [ebx]
or  eax, esi
mov [ebx], eax
おおお、すばらしい。なにがって〜と、レジスタが2つだけしか使ってませんよぉ。 ペ、ペアリングしてぇ〜(あぶなっ）。

さて、ペアリングしました(笑)。２桁の数字がクロックカウントで、 その次の-/1/2が何番目のDWORDに関する操作なのか、 u/vが実行するパイプです。 

00:-u shr ecx, 1
00:-v sub ebx, 8
LP:
01:1u mov eax, [edx]
01:-v add ebx, 8
02:2u mov edi, [edx + 4]
02:1v and eax, 0x7f7f7f7f
03:2u and edi, 0x7f7f7f7f
03:1v add eax, 0x7f7f7f7f
04:2u add edi, 0x7f7f7f7f
04:1v mov esi, [edx]
05:1u or  eax, esi
05:2v mov esi, [edx + 4]
06:2u or  edi, esi
06:1v and eax, 0x80808080
07:1u shr eax, 7
07:2v and edi, 0x80808080
08:2u shr edi, 7
08:1v add eax, 0x7f7f7f7f
09:1u xor eax, 0x80808080
09:1v mov esi, [ebx]
10:1u and eax, esi
10:1v mov esi, [edx]
11:1u or  eax, esi
11:2v add edi, 0x7f7f7f7f
12:2u xor edi, 0x80808080
12:2v mov esi, [ebx+4]
13:2u and edi, esi
13:2v mov esi, [edx+4]
14:2u or  edi, esi
14:1v mov [ebx], eax
15:2u mov [ebx+4], edi
15:-v add edx, 8
16:-u dec ecx
16:-v jnz short LP
実行確認したプログラムはこちら9-8bitmask.cpp (2005 bytes)です。 インラインアセンブラにアドレス渡す場合って、 
void *ptr;
DWORD a = (DWORD)ptr;
とかすればい〜んですね。ま、考えればすぐわかりますが。 そんなこんなで、ペアリングによって16clock/8byteの合成ルーチンができたわけで、 これならMMXもいらないぜぇ〜と思いきや、 おんなじことをMMXレジスタを使えばさらに半分のクロックになるわけで、 やっぱりMMXには勝てそうもありません(チ。 あれ？ってことは16clock/16byteになるんですか？ すげぇな、速すぎ〜。 ところでMMXって何本レジスタあるんだろ。ま、3本ぐらいあるだろ。 でわ。
Virtual Payment System100えん10えん1えんヘルプ

第10回 ： sin/cosに苦しむ
話の発端はsin/cosです。 そうです、例のテーブルは遅い!!の流れです。 第6回でsin/cosを書くのを諦めたと言いつつ、 まだ諦めてなかったのでした(笑)。

第6回の時点ではcosのテイラー展開を使ってました。 といってもわかりませんね。僕もわかりません(^^;。 そーいやsin/cosの近似ができたな〜程度に覚えていただけです。 ここで詳しくテイラー展開について説明するのは、 僕の墓穴を掘るだけなので(^^;、結果だけサクッと示したいところですが、 僕が後で参照できるように(笑)、式だけのせときます。 まずはテイラー(Taylor)級数。
f(x) = f(a) + (x - a)
f'(a)
1!
 + (x - a) 2
f''(a)
2!
 + ・・・ + (x - a) n
f (n) (a)
n!
 + ・・・
a = 0 のときを特別にマクローリン(Maclaurin)級数と呼びます。 で、こいつを使うと ex が展開できます。
ex = 1 +
x
1!
 +
x2
2!
 + ・・・ +
xn
n!
 + ・・・
ex に対してオイラー(Euler)の関係式 eiθ=cosθ + i sinθを 使うとsin/cosの展開式が得られます。
sin(x) = x -
x 3
3!
 +
x 5
5!
 - + ・・・
cos(x) = 1 -
x 2
2!
 +
x 4
4!
 - + ・・・
sin/cosの引数 x は一般には馴染みの薄いラジアンでの値ですよ。 まちがっても度数を入れてはいけません(^^;。ラジアンは360度を2πとして扱います。 まぁプログラムをした人なら知っているとは思いますが。

これでようやくスタートラインに立てました。 さて、sinとcosは同じテーブルを使えることはいいですね？
cos(x) = sin(x + 2/π) だからですね。 ということで、どちらか片方の関数の近似があれば十分です。 さて、そう考えてsin/cosの近似式を見なおすと・・・ sinよりもcosの方が次数が低いですね。 もちろん、数学的には無限に続く式なのでそれ自体はあくまで見かけですが、 ここではコンピュータで実装することが目的ですから適当なところで切ってしまって構いません。 厳密な値を得たければ近似をどんどん繰り返せばいいのですが、 今の目的はなるべく速くそれなりの値を求めたいので、 まぁ、いいとこ3つめの項で終わっちゃいましょう。

で、試してみました。 cosの近似を使って、どのくらいの誤差におさまるかな〜と。 結果としては、第6回で書いたとおりπ/2(45度)程度で0.02ぐらいで、 それ以上になるとちときついです。 ということで見切りをつけてました。

のですが、よくよく考えてみれば、 π/2あれば十分ではないか、と思い当たります。 というのも
cos(x) = sin(π/2 - x) だからです。つまり、π/2を超えたらあとはsinを使えばいいじゃんということです。 しか〜し、んじゃ、sinはどうやって求めるんだ〜と思うと、
sin(x) = cos(x - π/2) に立ち戻るわけで、ありゃりゃ意味ないじゃん。

ほかになんかないかねぇ〜と考えてみましょう。 おお、そういえば、倍角の公式なんてものがありましたなぁ。
sin(2x) = 2 sin(x) cos(x)
cos(2x) = 2 (cos(x) - sin(x))
ですね。うむむ、これもsin/cos両方の値が必要じゃ〜ん。

そんなこんなでまぁ、いろいろと考えたこの週末は全く実りがなかったのでした(爆)。 もしかしたら、sin/cos両用のテーブルを１周＋1/4周分用意するのではなく、 sin/cosそれぞれπ/2分だけ用意して計算で全周分を得ることも有利かもしれません。 あるいはsin/cosそれぞれπ/2分での近似計算を行うことで全周に対応すれば、 テーブルレスで無限分割に対応できますし。 ただ、cosの近似で2つめの項で止めたとしても乗算は2回必要なので、 それを考えるとテーブルと張り合うのはかなりきついでしょう。 ちなみに2回の乗算とは、度数（分割単位）からラジアンへの変換時と、 2乗の計算のときのことです。 ということは、角度をラジアンで扱っていれば乗算は1回ですな。 そのとき、32bit長、16bit固定小数点とすれば 

int Cos(int x)
 {
    x >>= 8;
    x = x*x;
    x >>= 1;
    x = (1 << 16) - x;
    return x;
 }
となります。この式だけ見ればかなりかっこえ〜んですがねぇ。 今回は内容が全く無いですが、勘弁してくださいよ。でわ。
Virtual Payment System100えん10えん1えんヘルプ

バーチャル支払いシステム
暁のコーダ部屋のそれぞれの記事が面白い、有用だと思われた場合、対価として適当と思った金額をクリックします。これによって、あなたはバーチャルにお金を支払ったことになり（つまり、支払ってない）、そのバーチャルお金はバーチャルに僕の口座へ振り込まれるという、誰のふところも痛まない、いいシステムなのです。

sanami@aya.or.jp