HOME | PRODUCT | BBS | CODE
Code | Memorial | Sample | Reference
List | -10 | -20 | -30 | -40 | -Latest
since 2000/10/01
#21 (2000/06/26 )
 ほんわかさんの飽和減算
#22 (2000/07/15 )
 固定小数点における正しい乗算
#23 (2000/09/07 )
 PSET for WonderWitch
#24 (2000/09/10 )
 PSET for WonderWitch vol.2
#25 (2000/09/12 )
 PSET for WonderWitch vol.3
#26 (2000/10/01 )
 無圧縮PNGの怪
#27 (2000/10/22 )
 固定小数点における遅くはない乗算
#28 (2000/10/26 )
 C++で始めるお手軽オブジェクト指向
#29 (2000/11/03 )
 真・C++で始めるお手軽オブジェクト指向
#30 (2001/01/04 )
 色抜き転送 for WonderWitch

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

第21回ほんわかさんの飽和減算
飽和加算と聞くと、どうしても、「ほんわかさん」と思って、 なんとなくなごんでしまいます。 それはともかく、 長らく飽和減算は考えていなかったのです。 というのも、飽和加算の方は、 光の効果を出すために使うとして、 飽和減算って、何に使うのよ、と思っていたのです。 しかし、つい先日、 あるデモで飽和減算使っていて、はぁ、 こうやって使うのねぇ〜と思い知らされました。

さて、飽和減算って何や、という人のために、 プログラムで示しましょう。

out = img1 - img2;
if(out < 0)
   out = 0;
ということです。ピクセルのRGB値に対して適用すれば、 画像から画像を引いて、引きすぎるところは黒にする、 ということです。

さて、飽和加算に関しては、以前に考えた

((img1 + img2) - MASK) or MASK
が使えます。 しかし、 この手法は飽和減算に適用することができません。 理由は簡単で、 マスクにおける飽和する要素(計算結果が負の値になるため0にした要素)の部分のbitを1にすると、
((img1 - img2) + MASK) & (not MASK)
としなければならないからです。

このことには最初から気がついていたので、 飽和減算はあきらめてました(^^;

さて、先日、やねさんに飽和加算の

((img1 + img2) - MASK) or MASK
を知らせたところ、 メールでSYNさんのページの プログラミングトピックの飽和加算・減算で紹介されてますよ〜と教えていただいたので、 わ〜ぃ、と思って見にいってきました。 ・・・このページ、前に見たことある〜。 僕も乱数の発生方法を検索したときに訪れていたのでした(^^;

で、ふたたび見直してみると、 やっぱり、飽和減算の式が気になったのでした。 で、いろいろ考えました。

ふと思いついたのですが、 飽和加算との対称性を考えれば、同じことができるはずです。 ということから

// SYNさんのページから引用
u_short SubBlend(u_short c0, u_short c1)
{
    u_short c, m;
    c = (((~c0 & c1) << 1) + ((~c0 ^ c1) & 0x7bde)) & 0x8420;
    m = (( c >> 5) + 0x3def) ^ 0x4210;
    return (c0 - c1 + c) & m;
}
の最後の行を
    return ~((~c0 + c1 -m) | m);
と書きかえられることを発見しました。 要するに、飽和したところを00にしたいので、 その前段階として、11にしてからnot演算でひっくり返すわけです。

しかし、いけてません。 演算数が多すぎます。 飽和加算と逆のことをするのになんで長くならなきゃいけないのでしょう。

ということで、政治が変わらないならコードを変えてやる、 と考えました。 30分後、かっちょえぇ〜のを考えました。

    return (c0 | m) - (c1 | m);
ビューティホー! これなら演算数は増えずに、レジスタ数も増やさず、 いけそうです。(c1 | m)を引くところがちょっといやな気もしたのですが、 この演算をする前に(c0 | m)を計算していれば、 mのレジスタをつぶせますから大きな問題ではないような気もします。

いちおう、思考の順序を簡単に書くと、 最初は、c0-c1の飽和フラグを求めるところの改善を考えていました。 これはあきらめました。 次に、対称性を考えて、 前者の手法を発見しました。 c0の値自体を使わなくなるので、 not c0の値をレジスタに保持しておけば、 演算数は増えないはず、と思い、レジスタ数的にどうなるかなぁ〜と、 試しに書いてみましたがいけてませんでした。 そして、次に書いたメモ。

FF-b
a-b=(a+FF)+(FF-b)
で、数分後、
    return (c0 | m) - (c1 | m);
を得ました。 ちなみに、FF-bは、not bのことです。 わかるような、わからないような思考の軌跡ですね。 でも、いろいろメモするとそこから思いつくこともあるってことです。

ということで。でわ。

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

第22回固定小数点における正しい乗算
ここのところ、食品関係の問題が噴出しています。 埼玉県では、 間違えてハムがO157で汚染されたという検査結果を公表してしまったとかで(詳しい経緯はしりません)、 損害賠償を税金でするわけにもいかず、 埼玉県庁舎の食堂でハムを積極的に使うということでお詫びの気持ちを示すそうです。 さて、食品関係でこのようなことが起こると、 決まって責任のある立場の政治屋がその食品を食べるというのが慣例です(笑)。 今回のハムの件では埼玉県知事がハム料理を食べて、

「塩加減がいいね、このハム」

と言ってました。 それにしても、そのような役職にある人の嫌いなモノに問題があっても、 やっぱり食べるんでしょうか。

官僚「大臣、食べてください」
大臣「わしは嫌いじゃ」

う〜ん、楽しそうです。でも、その程度ならまだいいほうかもしれません。 これが、青汁とかだったら・・・

記者「お味はどうですか?」
大臣「うまい!」

・・・責任問題にならんですかね(笑)。

さて、アセンブラ1年生の僕は、乗算命令なんて使ったことがないのでした。 ですから、命令の動作を知っているわけもなく、 たとえば16bitシフトの固定小数点の値の乗算は、オーバーフローしないように

c=(a>>8) * (b>>8)
としていました。
c=(a>>16) * b
は論外ですね。

いちおう、なぜかを説明しておきましょう。 誤差を含まない演算を

ct=a*b
とします。固定小数点で考えると難しいので、 普通の値として考えるとして、 ((a>>8)<<8)に相当する値をa8とします。 また、このときの誤差をεa8とします。 つまり、
a = a8 + εa8
です。同様に、b8、εb8、a16、εa16を定義します。 それでは検証してみます。

c=(a>>8) * (b>>8)
における誤差をε0とすれば、
ct=c0 +ε0 = a8 * b8 +ε0
であり、
ct=a*b = (a8 +εa8) * (b8 +εb8) = a8 * b8 + a8*εb8 +b8*εa8 +εa8*εb8
ですから、
ε0=a8*εb8 +b8*εa8 +εa8*εb8
となります。 次に、
c=(a>>16)*b
における誤差をε1とすれば、同様にして
ε1=εa16 *b
となります。 このときのε0とε1の大小を比較すればよいわけです。 さて、16bitシフトの固定小数点値であることを 思い出すと、それぞれの値の範囲を決めることができます。
0 =< a,b,a8,b8,a16 < (1<<16)(符号なしとして考えて)
0 =< εa8,εb8 < 1/(1<<8)
0 =< εa16 < 1
それでは両者の最大誤差を計算してみましょう。
ε0= (1<<16)*(1/(1<<8)) + (1<<16)*(1/(1<<8)) + (1/(1<<8))*(1/(1<<8))
   = 2*(1<<8) + 1/(1<<16)
   := (1<<9)
ε1= (1) * (1<<16)
   = (1<<16)
この結果から
c=(a>>8) * (b>>8)
のほうが一般的に誤差が小さくなります。 しかし、今回の場合について言えば、 こんな式をずらずら並べなくても
c=(a>>16) * b
を使わないほうがいい理由は明白です。 この式では、せっかく固定小数点で表現したaが、 ただの整数値になってしまいます。 a=1.5が計算する上でa=1になってしまうってことです。

さて、ようやく本題に入れます。(前置きが長いよ・・・)
x86アセンブラレベルで考えれば、2つの値がeax, ebxに入っているとして、

mul eax, ebx
で、上位32bitがedxに、下位32bitがeaxに入るわけです。 ですから、 長々と説明してきた
c=(a>>8)*(b>>8)
なんて式を使わずに、計算できるのです。 しかも、誤差なしで。

それはいいとして、ここで問題です。 C言語ではどう書けばいいのでしょう? なにも考えずに書くのであれば、

c=(a * b)>>32;
となるはずです。コンパイラが式全体を見て、 勝手に適したコードを吐き出してくれるならこれでいけそうな気もします。 しかし、コンパイラの立場に立ってみると、 この式がオーバーフローを期待しているかどうかを判断するのは無理です。 まぁ、プログラムの文脈処理をして・・・いやいや、無理だろう、それは。 当然ながら、コンパイラは仕様にそってコンパイルしてくれなければ困ります。 したがって、
DWORD a, b, c;
c = (a * b) >> 32;
と書いたら、c は常に0になります。
2000/08/02 注:インテル系ではシフト値が 「5ビットにマスクされ」(=n%32)という仕様のため、 cにはa*bが入ります。
ロベールさん、ご指摘ありがとうございました。

これを期待したように計算するためにはどうすればいいでしょう。 答えは、basetsd.h にありました。

typedef unsigned __int64 DWORD64, *PDWORD64;
おお。これだ。 ということで、正解は
c = (DWORD)((((DWORD64)a) * b) >> 32);
となりました。 でも、DWORD64*DWORD64の計算がどうなっているのかが気になるところです。 となれば、試して見ればいいのです。
-----------------------------------------------------
#include <windows.h>
void main(void) {
    DWORD64 a, b, c;
    c = a * b;
 }
-----------------------------------------------------
をコンパイルしてソースを吐き出すと
-----------------------------------------------------
	mov	eax, DWORD PTR _b$[ebp+4]
	push	eax
	mov	ecx, DWORD PTR _b$[ebp]
	push	ecx
	mov	edx, DWORD PTR _a$[ebp+4]
	push	edx
	mov	eax, DWORD PTR _a$[ebp]
	push	eax
	call	__allmul
	mov	DWORD PTR _c$[ebp], eax
	mov	DWORD PTR _c$[ebp+4], edx
-----------------------------------------------------
だそうで。 ・・・おぃ、関数呼出してんよ〜。 その関数はいずこに? ソースが見当たらないので、こんなときはえぇぃっと、 VCを立ち上げて、 c=a*bの行にブレークポイントをしかけて実行します。 んで、停止したら、ステップイン(F11)で関数内部に入ります。 ありゃ、LLMUL.asmがどこにあるか聞かれました。 そんなんしらんので、キャンセルを押します。 そうすると、あら不思議、アセンブラコードを見ることができました。 ご丁寧にもラベル名つきです。Debugライブラリ万歳(笑)。 その結果。
-----------------------------------------------------
_allmul:
004010F0   mov         eax,dword ptr [esp+8]
004010F4   mov         ecx,dword ptr [esp+10h]
004010F8   or          ecx,eax
004010FA   mov         ecx,dword ptr [esp+0Ch]
004010FE   jne         hard (00401109)
00401100   mov         eax,dword ptr [esp+4]
00401104   mul         eax,ecx
00401106   ret         10h
hard:
00401109   push        ebx
0040110A   mul         eax,ecx
0040110C   mov         ebx,eax
0040110E   mov         eax,dword ptr [esp+8]
00401112   mul         eax,dword ptr [esp+14h]
00401116   add         ebx,eax
00401118   mov         eax,dword ptr [esp+8]
0040111C   mul         eax,ecx
0040111E   add         edx,ebx
00401120   pop         ebx
00401121   ret         10h
-----------------------------------------------------
んでわ、説明。 要するに、64bitの上位32bitが両方0なら32bit同士の乗算なのです。 それをまず判定しています。
004010F8   or          ecx,eax
で判定しているわけですね。んで、どっちか片方でも32bit値でなかった場合には、 このライブラリを書いた人もいや〜んと思ったのでしょう、 hardに飛びます。hardの部分では32bitずつに分けて計算しています。 ここでmulが3つなのに注目です。 上位32bit同士の乗算は、64bit部には影響しないので計算しないのですね。 Releaseバージョンではどうなってるかなぁ〜と思ってやってみようとしましたが、 ブレークが無効になるので、 先頭からF11を連打・・・断念しました。くそっ

さてさて、 上のコードを見る限り、 ちょっとばかし余計なことをしているわけです。 いっそのこと、

c=(DWORD)((DWORD64)(a*b));
とかで、条件分岐をキャンセルできると気持ちいいのですが、 これではa*bをDWORDで計算した後に拡張するので使えません(笑)。 それでは、ということで今度は
-----------------------------------------------------
#define MUL(a, b) \
         _asm { \
          ....
         }
-----------------------------------------------------
としましたが、展開時にエラーになってしまいました。 エラーメッセージでasmの前のアンダーバーが2つに増えるところが怪しいです。 なんとなく、VCの設計ミスな気がしますが、 できないことにこだわってもしょうがないので次。 最後の手段というか、当然のことながら残った手段ということで。
2000/07/18
原因がわかってから考え直してみると、設計ミスとも言えない気が。 アンダーバーが増えるのは設計ミス・バグのような気がしますけど。
-----------------------------------------------------
inline DWORD MUL(DWORD a, DWORD b) {
   _asm {
     mov eax, a
     mov edx, b
     mul edx
     shr eax, 16
     shl edx, 16
     or  eax, edx
   } }
-----------------------------------------------------
と。関数の戻り値はeaxに放り込んでおけばOKです。
2000/08/01 修正:
誤:imul eax, edx
正:mul edx
imulでは符号つきです。さらに引数2つの場合では上位32bitはどこにも保存されません。

ロベールさん、ご指摘ありがとうございます。

今回のまとめ。アセンブラ使いましょう(笑)。 あとは・・・ライブラリ内部のコードが面白いです。 コードの意味がわかるとよいですねぇ。 ほんとはスキャンコンバージョンについて書こうかなぁ〜と思っとんたんですが、 今後に後回し。というか、書こうと思ってファイルを開いたら、 この回のがあったので、あ、これ使っとけって。(笑)
そんなところで。でわ。 第22+回: 固定小数点における正しい乗算、その後(2000/07/18)


Diracさんからメールを頂きました。メールをそのまま掲載するのはアレなので、 要約です。

#define MUL(a, b) \
            __asm{ \
                ...
            }
が展開時エラーになるとのことですが、これは次のように書けば良かったと 思います。
#define MUL(a, b) \
            __asm{ \
                __asm ... \
                __asm ... \
                ...
            }

早速試してみました。 2分後・・・駄目でした。 う〜ん、残念。あ、そうそう、_ _asm と _asm はどっちでもいけます。 いや、この場合はどっちでもいけないけど。(わかんないって・・・)

数時間後、 他のことを調べるために、 MSDNライブラリを探索しているとC++プログラマーズガイドにインラインアセンブラの 章があるのが目に入りました。 もちろん、ひととおり読んだつもりですが、 細かい仕様を覚える気はなかったので、 最低限必要な項目を流し読んだくらいだったかもしれません。

さて、このとき目に止まったのは、 インラインアセンブラの章の中の 「_asmブロックのC++のマクロとしての定義」 です。

そこを見ると・・・Diracさんのご指摘のように説明されていました。 マクロは1行に展開されるので、デリミタとしての_asmが必要なようです。 しかし、今回のエラーはこれが原因ではありません。 最初の_asmを発見した時点でエラーが出ているのです。

そのページを最後までちゃんと読むと・・・

C のマクロとして記述された __asm ブロックは、引数を取ることができます。 ただし、通常の C のマクロとは異なり、__asm マクロは値を返すことができません。 したがって、C/C++ の式では、__asm マクロは使用できません。
こ、これだぁ〜。確かにそう言われてみれば、 そうです。関数の戻り値は eax に放りこんでおけばいいですが、 マクロに戻り値など、規定されていません。 となると、戻り値を代入しようとしたところで、 代入する値がどこにあるかわからないわけです。

さて、問題がわかれば対処のしようがあるってもんです。

c = MUL(a, b);
MUL(c, a, b);
の形式にしてインラインアセンブラで c に代入すればいいのです。 そのように変更したところ、無事、コンパイルできました。

ということで、16bitシフトの固定小数点値の乗算をマクロで記述するには、

-----------------------------------------------------
#define MUL(c, a, b) __asm { \
    __asm eax, a \
    __asm edx, b \
    __asm mul, edx \
    __asm shr eax \
    __asm shl edx \
    __asm or  eax, edx \
    __asm mov c, eax \
   }
-----------------------------------------------------
とすればインライン関数版と同等のコードが得られるということになります。
2000/08/01 修正:
誤:__asm imul eax, edx
正:__asm mul edx
imulでは符号つきです。さらに引数2つの場合では上位32bitはどこにも保存されません。

ロベールさん、ご指摘ありがとうございます。

と、ここまで書いて学校に行って、 帰りの電車の中で実際にこれを使おうとして、 重大な欠点を発見しました。 それは一体、なんでしょう? 実際に使ってみれば「そりゃそうだ」とわかることです。

答えは、引数に関数の戻り値を使えない、です。 他にも、配列とかがダメそうです。 理由は簡単、インラインアセンブラに展開したときに、 命令が実行できないからです。

MUL(c, Cos(a), b));
と、書いた場合、これは
	__asm eax, Cos(a)
なんて展開されるわけですから、無理なのは当然です。 え?それじゃ、やっぱマクロではダメじゃないかって? 結論を出すのはまだ早すぎます。 ちゃんと、不要なオーバーヘッドを回避した上で、 この問題を回避することは可能です。 その方法とは・・・
-----------------------------------------------------
#define MUL(c, a, b)	\
	DWORD tempA = a;	\
	DWORD tempB = b;	\
	__asm {				\
		__asm mov  eax, tempA	\
		__asm mov  edx, tempB	\
		__asm mul  edx			\
		__asm shr  eax, 16		\
		__asm shl  edx, 16		\
		__asm or   eax, edx     \
		__asm mov  c,   eax		\
	 }
-----------------------------------------------------
2000/08/01 修正:
誤:__asm imul eax, edx
正:__asm mul edx
imulでは符号つきです。さらに引数2つの場合では上位32bitはどこにも保存されません。

ロベールさん、ご指摘ありがとうございます。

簡単なことですね。 tempAとtempBが不要なオーバーヘッドではないの? と思ってしまった人は負けです。 この一時変数は簡単な最適化をかけただけで不要であれば削除されます。 ですから、例えば、

DWORD x, y, z;
MUL(z, x, y);
のように使っている場合は、 実際のアセンブラコードではtempAおよびtempBを確保し、 そこに書き込むといったことはなされません(確認済み)。

さて、ここでなるほどと思ってしまった人はまだまだ青いです。 このマクロにはアホな欠点があるのです。 もちろん、対処できるので、 最初っから対処したマクロを示してもいいのですが、 途中の過程も重要だろう、ということでわざわざ長くしておきます。 というとかっこいいですが、単に文章を長くしたかっただけ、 とかいう深層心理が強く働いたとかいうことは・・・多分、ないんじゃないかな〜。

正解:同じブロックで2回使うとtempA/tempBが多重定義になる(笑)

そゆことなので、使うときは全部をブロック { } で囲ってください。

ということで、22回のコードは2つの間違いをおかしていたのでした。 いやはや、まったくもっていけてねぇぜぇ〜。 Diracさん、ご指摘、ありがとうございます。 今後も穴を見つけたらこっそり教えてください。

あ、そうそう、僕のことは 青い負け犬 と呼んでください(笑)。 それでは。

2000/08/01
ロベールさんにご指摘いただいたように、 符号付きと符号なしをかなりミックスしてお届けしましたので、 それはそれは複雑な味わいになったかと思います。 そういうわけで、22回のコードは、さらに+1の間違いをおかしていたのでした。 ひぇ〜、まったくもっていけてねぇ〜

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

第23回PSET for WonderWitch
さて、しばらく更新していなかったのはわけがあります。 夏コミ+α、いや違った、α+夏コミで忙しかったのが一番の要因ですが、 夏コミ後に更新していないのは、夏コミ、落としたのが原因です(だめだ〜)。 市販のゲームでも「○のありか」のようにバグだらけ〜というものがありますが、 そのようなゲームを出したとき、日記(またはそれに類するもの)を書くのは開発者側にとって、 非常にマイナスなんじゃないかなぁ〜と考えていたのです。 日記を読めば開発状況がわかってしまうということもありますが、 ゲームのサポートが深刻な状況なのに、へらへらと日記を更新されたのでは、 たまりません。とか思っていたのですが、 こんなページでも読んでいる人がいるということがわかったので、 んじゃ、更新すっかな〜ということで更新するのです。

ということで、 こんなとこ更新するならさっさとパッチだせーという方は、 どうぞ遠慮なく匿名感想フォームから送信してください。 開発スピードは変わりませんが(すんません、今いっぱいいっぱいなんです)。

さて、今日の夕刊を読んでいると、 参院選挙における1票の格差が5倍以内なら合憲という最高裁の判決がでていました。 この判決は、裁判官15人のうちの10裁判官の多数意見によるということですが、 本気なんでしょうか。もし、この多数決に1票の格差を導入したら、 2倍で同数、5倍なら大差で違憲という判断になるのです。 まったくもって理解できません。
過疎地に配慮とか言う話は別の話です。念のため。

今日のお題はWonderWitchなのです。 WonderSwanとゆー携帯ゲームマシンがあるのですが、 WonderWitchは、そのWonderSwan用のプログラムを開発するためのキットです。 で、なぜWonderWitchかというと、 WonderWitchが適度に遅いマシンで、 最適化が面白そうというところにつきます。 ただ、白黒なので「これがカラーならやるんだけどねぇ」と周りに吹聴していたところ、 WonderSwanColorの発売が決定し、 WonderWitchもライブラリが対応するというアナウンスがされたので、 穴にはまってしまったのです。

で、休憩時間に情報を検索していたところ、 ネタを発見したのでいてもたってもいられなくなって、 更新することにしたのです。ほんとは、別の内容をすでに書いていたのですがねぇ。

ネタというのは、WonderWitchにおけるPSETの実装です。 (x,y)に任意の色(4色から)を打つPSET関数は
unsigned int buffer[SCREENW * SCREENH * 8];

/*-----------------------------------------
setPixel
任意の位置に点を打つ
x ... X座標
y ... Y座標
c ... 階調(00,01,10,11)
-----------------------------------------*/
void setPixel(int x,int y,int c)
{
	/*0000000000000011 -> 1000000010000000*/
	unsigned int bit = ((c&2)<<14) | ((c&1)<<7);

	buffer[(x&~7) + (y&7) + (y&~7) * SCREENW] |= bit >> (x&7);      
}
石田さんのページ [http://homepage1.nifty.com/open-prog/]から引用
のようになるようです。なるようです、というのも、 僕、まだWonderWitchもってないんでわかりません(笑)。 で、見た瞬間にマスクを作ったりする手法が使えるな〜 ということを思ったのです。

まず、最初にすることは、下位2bitに格納されている色情報を、 7bitの間隔が空くように編集することです。
0000 0000 0000 00ab
        ↓
0000 000a 0000 000b
a, b = {0,1}

これは、マスクを作るように考えれば、
c = c + [0000 0000 1111 1110];

a = 0:
   0000 0000 0000 000b
+) 0000 0000 1111 1110
----------------------
   0000 0000 1111 111b

a = 1:
   0000 0000 0000 001b
+) 0000 0000 1111 1110
----------------------
   0000 0001 0000 000b
とすることで移動できます。 あとは、andでマスクをかければゴミを掃除できます。

そうなれば、書き込むほうも注目すると、シフトは左シフト1回でいいはずです。
src = 0000 000a 0000 000b

x&7 == 0:
dst = a000 0000 b000 0000
    = src << 7

x&7 == 1:
dst = 0a00 0000 0b00 0000
    = src << 6

x&7 == 2:
dst = 00a0 0000 00b0 0000
    = src << 5
以下略
シフトの量は、7 - (x & 7)になりますね。 これはアセンブラでは、axにxが入っているとすると、
and ax, 7
mov cx, 7
sub cx, ax
となり、レジスタが二つ必要なので、ちょっとやらしい計算ぽい気がします。

ここで、7 - (x & 7)の式の意味を考えると、 実は、(-x) & 7でもいいことがわかります。 式の持つ意味は、xの下位3bitを反転したもの、です。 ということは、xを反転して下位3bitだけ取り出せば、 結果は同じはずです。

たとえば、x=8を考えて見ます。この場合は、x&7 == 0 ですから、 シフト量は7です。 さて、xを反転して下位3bitを取り出してみると
x      = 0000 0000 0000 1000
~x     = 1111 1111 1111 0111
~x & 7 = 0000 0000 0000 0111
おっけーです。んでは、x=2では…
x&7 == 2 → dst = src << 5

x      = 0000 0000 0000 0010
~x     = 1111 1111 1111 1101
~x & 7 = 0000 0000 0000 0101
おっけーですね。ということで、 7-(x&7) = (~x) & 7でもいいことがわかりました。 これなら、
not ax
and ax, 7
ですから、1命令減らせて、かつ、レジスタも1つで済みます。 インデクスの計算部は…せいぜいテーブルを使うぐらいしかない気がしますね。

そんなこんなで、
void setPixel(int x,int y,int c)
{
	c = (c + 0x00fe) & 0x0101;
	buffer[(x&~7) + (y&7) + (y&~7) * SCREENW] |= c << ((~x) & 7);
}
となりました。 行を詰めて書いたおかげで速くなった気がします(笑)。

それはそうと、この関数は、 よくよく考えて見ると、0クリアされていることが保証されていないので、 まずクリアしてから書き込むべきかな〜という感じです。 というわけでクリアするためには、マスクをかける必要があるわけです。 ところが、
mask = 0xfefe;
shift = (~x) & 7;
dst &= mask << shift;
なぁんてことができません。理由は簡単、シフトしたあとの右側が空になってしまうからです。 ということで、ここは一発、インラインアセンブラで
mov mask, 0xfefe
not x
and x
rol mask, x
and dst, mask
としたいです。 インラインアセンブラを使わずになんとかできないでしょうか?
2000/09/08 追記
そもそも rot reg, reg がないようです(笑)

一つのアイデアとしては、
      xxxx ?xxx xxxx ?xxx
or)   0000 1000 0000 1000
     --------------------
      xxxx 1xxx xxxx 1xxx
and)  1111 a111 1111 b111
     --------------------
      xxxx axxx xxxx bxxx
とうことが考えられますが、andで使う値を作るためにシフトしているので、 問題は改善されていません(笑)。

しかし、アイデア的にはいい線を行っています。 こうすればいいのです。
      xxxx ?xxx xxxx ?xxx
or)   0000 1000 0000 1000
     --------------------
      xxxx 1xxx xxxx 1xxx
xor)  0000 A000 0000 B000
     --------------------
      xxxx axxx xxxx bxxx
A = ~a
B = ~b
ということで、0クリアされてない点への書き込みはこんなふうになりました。
void setPixel(int x,int y,int c)
{
	int mask = 0x0101;
	c = ((c ^ 0x0003) + 0x00fe) & mask;
	int sh = (~x) & 7;
	buffer[(x&~7) + (y&7) + (y&~7) * SCREENW] |= mask << sh;
	buffer[(x&~7) + (y&7) + (y&~7) * SCREENW] ^= c << sh;
}

ところで、サイト移転します。 理由は簡単、Webnikが潰れるOCNに移行するためです。 ただ、OCNのサービスは僕の要求と異なるので、 ほかのプロバイダを探しています。 で、申し込みの書類を請求しているところなんですが、一向に届かないので申し込めません。 ここのサーバーは10/31まで使用できることになっているので、 9月中に移転、一ヶ月くらい告知をしたいと考えています。 OCNに移行したユーザは12/31まで移転告知を出せるのに、 移行しないユーザはだめなのです。さすがWebnikといったところですか(嫌味)。 http://webs.to/D5./でなら問題なくアクセスできる予定です。

パッチの公開についても、 新サイト移行を目処に日夜がんばっていますので、 長い目で見守っていただきたく思います。 と、ここに書いてもしょうがないですか。 そんな感じで、次の更新は新サイトで、と目論んでおります。 そんなとこで。でわ。

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

第24回PSET for WonderWitch vol.2
さて、 舌の根も乾かぬうちに更新なのです。 「次の更新は新サイトで、と目論んでおります。」 とか言っておきながら3日後に更新するとは破廉恥極まりないのです。 これではせっかく見に来てくれている人も付き合ってられません。 1ヶ月半も更新しなかったと思ったら、 ちょっと見ぬ間に2回も更新しているのです。 いったい、どういうスパンで見にこいというのでしょう。 という感じなので、前回の評価ボタンはまだ押されてないのです(笑)

それはさておき、 ただ単に速いコードを示すのであれば、 他のサイトに行って、速いコードをゲットしてコピペすればいいのです (むちゃむちゃな話の展開だな…)。 このページは、1クロック削ることの喜びと苦しさを伝えるためにあるのです。 で、実際のところ、 1クロック削るのに、30分はかかっているのです。 ということで、みなさんは、 10クロック以上削ったPSET関数を使ったゲームは300分以上遊んで欲しいのです (なんのこっちゃ)。

そういう背景があるので、 結果を示して解説だけするよりは、 途中の思考錯誤(これはこれで正しい気もする)を書いておくと、 面白いかなぁという気がしてるのです。 なにより、これを読んだ人が自分もやってみようという気になれば、 僕の勝ちです(^^;。

さて、話は前回に引き続き、 WonderWitchにおけるPSET関数の最適化です。 なぜこんなことをしているかというと、 WonderWitchが手元にないからで、 すごそうなプログラムをダウンロードしてきても、 それを試せないのです。 しょうがないので、そこらにあるコード片を最適化してやれ、 ということなのです。さみしいですね。

さて、前回のコードを書いていたときは、 仮想画面幅が可変であると思っていたのですが、 よくよく考えて見れば、固定サイズの画面におけるフレームバッファのサイズは、 当然固定であるわけで、書き込む先のアドレス計算を最適化することができるのです (わかりにく言いまわしだな…)。

つまり、前回、
buffer[(x&~7) + (y&7) + (y&~7) * SCREENW] |= bit >> (x&7);      
のコードに対して、

インデクスの計算部は…せいぜいテーブルを使うぐらいしかない気がしますね。
とほざいていたのですが、SCREENWは定数なので最適化が可能だった〜、 ということなのです。 ってゆーか、SCREENWって書いたら普通は定数だろ〜。気づけよ〜>僕

さて、前回のプログラムはC言語だったわけですが、 WonderWitchのPSETは mapiさんのページ にも掲載されているのでした。 しかし、根性のない僕は「アセンブラ読む気力がねぇ〜」とやる気0モードだったのでした。 それでは人間、いけません。 心を入れ替えてアセンブラとしゃれこみましょう(無茶苦茶だ…)。

最適化〜の最初の1歩は、問題の解析です。 というとかっこいい気がしますね。 お題は、PSET関数ということで、

  1. 書き込むアドレスの計算
  2. 書き込む値の計算
  3. 書き込み
の3つの小さな問題に分割できます。 ここで重要なのは、それぞれの問題が★なるべく★独立な問題となるように分割することです。 今回の場合は、2と3は完全に独立ではないことを心にとめておいてください。 前回は2に重点をおいて考察を行いました。

それでは、まず、書き込むアドレスの計算から考えます。 アドレスの計算は、ベースアドレスからのオフセットとして計算するわけですが、 まぁ、簡単に言えば、C言語の配列のインデクスを計算するようなものです。 さて、SCREENWはどうやら224=16x28のようです。 ということで、計算式は
addr = (x/8)*16 + (y&7)*2 + (y/8)*16*28
mapiさんのページから引用
となっています。 一つづつ見ていきます。まず最初の項の
(x/8)*16
は、意味を考えると、xの下位3bitを切り捨てて、2倍する、です。 これはいいでしょうか。手順を図示すると下図のようになります。
x        : abcd efgh ijkl mnop
x/8      : 000a bcde fghi jklm   // 右3シフト
(x/8)*16 : bcde fghi jklm 0000   // 左4シフト
一目瞭然ですね。 ということは、結果を見ると、このように書けます。
(x/8)*16 = (x & 0xfff8) << 1

となると、第3項も同様に変形することができます。
(y/8)*16*28 = ((y & 0xfff8) << 1) *28

そゆことで式を整理して〜とするとこんな感じになります。
((x/8)*8 + (y&7) + (y/8)*16*14)   *2
((x & (~7)) + (y & 7) + (y & (~7)) *28) *2
((x & (~7)) + (y & 7) + (y & (~7)) *7 *4) *2
((x & (~7)) + (y & 7) + (y & (~7)) *(8-1) *4) *2

さて、このあたりまでは普通です(多分)。 でも、(8-1)は趣味です。 で、アセンブラにすると、こんな感じですか。
[bp +4] → x座標
[bp +6] → y座標

mov ax, [bp +4]
and ax, ~7			// x ok

mov bx, [bp +6]
and bx, 7
add ax, bx

mov bx, [bp +6]
and bx, ~7
mov cx, bx
shl bx, 3
sub bx, cx			// x7 ok
shl bx, 2

add ax, bx
add ax, ax			// Ok
問題は、これが速くなったのかどうか、ということですが…13命令ですか…。 と思いきや、シフト命令は3クロックかかるのでした。 ということで、改良すべきですね。

それではシフト命令を減らす方向で検討してみましょう。 問題の中心は、bxを28倍する部分です。
mov cx, bx
shl bx, 3
sub bx, cx			// x7 ok
shl bx, 2
シフト命令をなくしてしまいましょう。
mov cx, bx

add bx, bx
add bx, cx
add bx, bx
add bx, cx			// x7 ok

add bx, bx
add bx, bx			// x4 ok
参考:mapiさんのページ
1クロック減ったようです。 スタンダードな変形です。なんか他に面白そうな変形はないでしょうか?

ちゃんとあります。28=32-4です。
mov cx, bx

shl bx, 5			// x32 ok

add cx, cx
add cx, cx			// cx = cx x 4

sub bx, cx
シフト命令が復活していますが、同じ7クロックです。 これが限界でしょうか? あった〜、と思ったら勘違いでした。 まぁ、よくあることです(笑)。 勘違いの中身は、パーシャルレジスタ幅です。 冗談として載せておいてもいいんですが、 なにしろ勘違いしてるので、論理に破綻をきたしているので、 読む人はわけがわからなくなるのでやめておきます。

さて、前回では書き込む値の計算を
	mask = 0x0101;
	c = ((c ^ 0x0003) + 0x00fe) & mask;
	int sh = (~x) & 7;
	buffer[(x&~7) + (y&7) + (y&~7) * SCREENW] |= mask << sh;
	buffer[(x&~7) + (y&7) + (y&~7) * SCREENW] ^= c << sh;
としていました。ところが、8086コードを見ると…がぁん、 シフト命令でレジスタの値回の場合は5クロックなのですね。 だめじゃ〜ん。

とりあえず、書き込む値を計算する部分をアセンブラにしてみると、
mov ax, [bp +8]    // ax = c
xor ax, 0x0003     // ax ^= 0x0003
add ax, 0x00fe     // ax += 0x00fe
mov bx, 0x0101     // bx = 0x0101
and ax, bx         // ax &= 0x0101
mov cx, [bp +4]
not cx
and cx, 7          // cx = (~x) & 7

shl ax, cl         // ax <<= cx
shl bx, cl         // bx <<= cx
となります。とにもかくにも最後のshl二つが負担になっています。 これをなんとかしてみましょう。

で、shlを一つ減らすアイデアです。
もともと。
color  0000 000a 0000 000b
mask   0000 0001 0000 0001
↓
  shl color, CL (=3)
  shl mask , CL
↓
color  0000 a000 0000 b000
mask   0000 1000 0000 1000
これを、
color  0000 000a 0000 000b
mask   0000 0001 0000 0001
↓
color  aaaa aaaa bbbb bbbb
mask   0000 0001 0000 0001
↓
  shl mask, CL (=3)
↓
color  aaaa aaaa bbbb bbbb
mask   0000 1000 0000 1000
↓
  and color, mask
↓
color  0000 a000 0000 b000
mask   0000 1000 0000 1000
こうしてみましょう。 このとき、0000 000aからaaaa aaaaを3クロック以内で作れれば元より速くなります。 可能でしょうか?

可能です、というか、お手の物。詳しくは、過去ログ参照ということで。
shl color, cl
shl mask , cl

これは、

shl mask, cl
add color, 0x7f7f
xor color, 0x7f7f
and color, mask
こうなりました。これで2クロック削れたことになります。 ちなみに、xor color, 0x8080とすれば反転してマスクを生成できるので、 前回でc^=0x0003としていた部分も削れます。

さて、もう1個のシフトは削減できないでしょうか。 mapiさんのコードを見ると、テーブル参照しています。 そうか〜、テーブル参照か〜、 VC++のインラインアセンブラはデータ定義擬似命令が使えないから思いつきませんでした(笑)。 幸いなことに、LCCのインラインアセンブラは、 文字列をそのまま展開してくれるので、 VC++よりも高機能です(というか、低機能なのか?)。 ということで、テーブルを使ってみます。
shl mask, cl
これは、
add cx, cx
add cx, mask_data
mov cx, [cx]
注:cxレジスタでは間接参照はできません
これでさらに2クロック削れました。

それでは、全部まとめてみましょう。 わかりやすいように、C言語です(まだ話は続くのです)。
BYTE *VRAM;
void PSET(int x, int y, int c)
 {
	// アドレスを計算
	int addr = (x & (~7));

	int temp = (y & 7);
	addr += temp;

	temp = (y & (~7)) *28;
	addr = (addr + temp) *2;

	// マスクを生成
	int mask_data[] = {0x8080, 0x4040, 0x2020, 0x1010, 0x0808, 0x0404, 0x0202, 0x0101 };
	int mask = mask_data[x & 7];

	// 値を計算
	int color = c;
	color += 0x007e;
	color &= 0x0101;
	color += 0x7f7f;
	color ^= 0x8080;	// 反転して生成
	color &= mask;

	VRAM[addr] |= mask;
	VRAM[addr] ^= color;
 }
C言語だとかえって遅くなってるように見えますが(笑)。

さて、mapiさんのコードを見ると、 ふむふむ、色が0のときは書きこみ処理をしないのか。 確かにそうしたほうがよさそうです。 僕は、Pentiumの最適化から入ったので、 分岐は敵だったので、まさにそのようなコードになってました(笑)。

いまのプログラムでは、書きこみ動作を
          ???? ???? ???? ????
or mask   0001 0000 0001 0000
xor color 000A 0000 000B 0000
A=~a, B=~b
としているため、色が3のときにxor colorをスキップできるようになっています。 要するに、アルゴリズムが反転しているというわけです。 それはそれでもいいような気もしますが、 どちらかといえば、やはり色が0のときに速いほうが気持ちがいいでしょう(無理矢理)。

mapiさんのコードを見ると、ちょうどxor colorに相当する部分をスキップしています。 僕もそのようにするために考えて見ましたが、 xor colorをスキップするには、maskは
mask   1110 1111 1110 1111
の形式である必要があります。となると、 colorを計算するときに、
color&=mask
↓
color&=~mask
とせざるを得ないので、命令が増えてしまいます。 nandがあればよかったのですが。

そこで、ちょっと発想を転換してみましょう。 xor colorは実行するのです。 とすると、色0のときには、
color=0001 0000 0001 0000
となっていなければなりません。 ちょうどいいことに、今のルーチンはそうなっています。 ということで、 書き込む色を計算する部分をスキップできることがわかりました。

ということで、書きなおしてみると、
BYTE *VRAM;
void PSET(int x, int y, int c)
 {
	// アドレスを計算
	int addr = (x & (~7));

	int temp = (y & 7);
	addr += temp;

	temp = (y & (~7)) *28;
	addr = (addr + temp) *2;

	// マスクを生成
	int mask_data[] = {0x8080, 0x4040, 0x2020, 0x1010, 0x0808, 0x0404, 0x0202, 0x0101 };
	int mask = mask_data[x & 7];
	VRAM[addr] |= mask;

	// 値を計算
	int color = c;
	if(c)
	 {
		color += 0x007e;
		color &= 0x0101;
		color += 0x7f7f;
		color ^= 0x8080;
		mask  &= color;
	 }
	VRAM[addr] ^= mask;
 }
最後のほうのmask &= color;となっているのがポイントです。 それでは、アセンブラにしてみましょう。
	push es
	push di
	push dx
	push cx
	push bx
	push ax

	// アドレス計算部
	mov di, [bp +4]
	cmp di, 224
	jnc _skip		// そのまま

	mov bx, [bp +6]
	cmp bx, 144
	jnc _skip

	and di, ~7
	and bx, 7
	add di, bx

	mov bx, [bp +6]
	and bx, ~7
	mov cx, bx
	shl bx, 5
	add cx, cx
	add cx, cx
	sub bx, cx		// 32 - 4
	add di, bx
	add di, di		// 2倍
	add di, 0x2000	// 参考。なぜだか知りません(^^;

	mov bx, [bp +4]
	and bx, 7
	add bx, bx
	add bx, mask_data
	mov dx, cs:[bx]

	xor cx, cx
	mov es, cx		// まんま参考(^^;
	mov ax, es:[di]
	or  ax, dx

	// 書き込む値を計算
	mov bx, [bp +8]
	or  bx, bx
	jz  _skip_calc

	add bx, 0x00fe
	and bx, 0x0101
	add bx, 0x7f7f
	xor bx, 0x8080
	and dx, bx

_skip_calc:
	xor ax, dx
	mov es:[di], ax	// 書き戻し
_skip:
	pop ax
	pop bx
	pop cx
	pop dx
	pop di
	pop es
さて、問題はこれをどう使うかです。 フルアセンブラにするのは簡単かもしれませんが、 それでは僕が使えません(笑)。 ということで、lcc試食版のインラインアセンブラにしましょう。

まず、インラインアセンブラの書き方です。
_asm_XXX("\n ...アセンブリ言語の命令列\n", パラメタリスト)
だそうです。 ニーモニックを放り込むのはそりゃ簡単ですが、 まんま展開するだけのようです。 つまり、レジスタの保存は自前でやれっつーことです。

それはともかく、問題は引数の渡し方です。 lcc試食版のマニュアルを読むと、 いろいろ規約がありますが、
void pset(int x, int y, int c);
であれば、xはAXに、yはBXに、cはCXに入るようです。 それはいいとして、 もうひとつの問題は、ジャンプするときのラベル名です。 インラインアセンブラで書いた場合には、 (多分)同一ファイル内で使用すると名前が衝突します。 これを回避する手段は二つ考えられます。 一つ目はインラインアセンブラを関数でラッピングする方法です。 で、もう一つはラベル名を変えればいいのです。 せっかくなので、後者を使いましょう。

どうやって実現するかのヒントはマニュアルにあります。
3.6.1  ポート番号を文字列にうめこむ
これは、プリプロセッサの機能を使って実現できます。
#define inp(p)          _asm_c("\n\tIN\tAL," _q_(__eval__(p)))
用があるのは_q_( )のほうです。 そーゆーわけなので、
#define LABEL(num) _asm_a("_skip_calc_" _q_(num) ":\n")
としておき、
LABEL(3);
と書くと、
_skip_calc_3:
のように展開されます。 しかし、これではかなり面倒です。 なにしろ、プログラム中では、
pset(x, y, c, 8);
のように余計な引数が増えますので。 この引数は同一ファイル内では重複してはいけないので、 非常に鬱陶しいです。 要するに、重複しなければいいのですから、 こうしてしまいましょう。
#define LABEL _asm_a("_skip_calc_" _q_(__LINE__) ":\n")
__LINE__マクロは、プリプロセッサがファイル中の行番号に置き換えてくれます。 ということで、psetマクロはこんな感じになりました。 ながったらしいのは勘弁してくり〜
void _asm_pset(char *, int, int, int);
#define PSET(x, y, c)			\
	PSET_CORE(x, y, c, __LINE__)

#define PSET_CORE(x, y, c, n)	_asm_pset("\n"	\
	/* オリジナルコード:使えません(笑) */	\
	/* ここの時点では */					\
	/* x: AX register */					\
	/* y: BX register */					\
	/* c: CX register */					\
\
	/* まず画面内チェック */				\
	"\t cmp ax, 224 \n"						\
	"\t jnc _skip_" _q_(n) "\n"				\
	"\t cmp bx, 144 \n"						\
	"\t jnc _skip_" _q_(n) "\n"				\
\
	/* 破壊するレジスタを退避 */			\
	"\t push es \n"							\
	"\t push di \n"							\
	"\t push dx \n"							\
\
	/* アドレスを計算 */					\
	"\t mov di, ax \n"						\
	"\t and di, 0fff8h \n"					\
	"\t mov dx, bx \n"						\
	"\t and dx, 7 \n"						\
	"\t add di, dx \n"						\
	/* ここから28倍 */						\
	"\t and bx, 0fff8h \n"					\
	"\t mov ax, bx \n"						\
	"\t shl ax, 5 \n"						\
	"\t add bx, bx \n"						\
	"\t add bx, bx \n"						\
	"\t sub ax, bx \n"						\
	"\t add di, ax \n"						\
	"\t add di, di \n"						\
	/* アドレス計算終わり。 */				\
\
	/* マスクをゲット */					\
	"\t mov bx, ax \n"						\
	"\t and bx, 7 \n"						\
	"\t add bx, mask_data_" _q_(n) "\n"		\
	"\t mov bx, cs:[bx] \n"					\
\
	/* 書きこみ先のデータを読み込む */		\
	/* VRAMアドレスのオフセット? */		\
	"\t mov ax, 0200h \n"					\
	/* テストするときはesを更新しない */	\
	"\t mov es, ax \n"						\
	"\t mov ax, es:[di] \n"					\
	"\t or  ax, bx \n"						\
\
	/* 書きこむ値の処理 */					\
	"\t or  cx, cx \n"						\
	"\t jz  _skip_calc_" _q_(n)	"\n"		\
\
	/* 書きこむ色が0でない場合 */			\
	"\t add cx, 00feh \n"					\
	"\t and cx, 0101h \n"					\
	"\t add cx, 7f7fh \n"					\
	"\t xor cx, 8080h \n"					\
	"\t and bx, cx \n"						\
\
	/* 書きこみ実行 */						\
	"_skip_calc_" _q_(n) ":\n"				\
	"\t xor ax, bx \n"						\
	"\t mov es:[di], ax \n"					\
	"\t jp  _end_pset_" _q_(n) "\n"			\
\
	/* こんなところにデータ定義が */		\
	"mask_data_" _q_(n) ":\n"				\
	"\t dw 8080h, 4040h, 2020h, 1010h, 0808h, 0404h, 0202h, 0101h\n"	\
\
	/* 終了処理 */							\
	"_end_pset_" _q_(n) ":\n"				\
\
	/* 破壊したレジスタを復帰 */			\
	"\t pop dx \n"							\
	"\t pop di \n"							\
	"\t pop es \n"							\
\
	/* これで終わり */						\
	"_skip_" _q_(n) ":\n"					\
	"\n", x, y, c)
という感じで、がががっと書いてコンパイルしたところ…
too long asm
ひぇぇ〜、そりゃないよ〜。 そんなこと、マニュアルにはどこにも書いてないじゃんかよ〜。 もしかして、見やすいようにコメントまで入れたのが失敗ですか?(笑)。 ということで、不必要なコメントやタブ、スペースを削除してみましたが、 駄目でした。 ということは、最後の手段、dbでマシンコードを直接書いてしまいましょう(笑)。 ほんとは、やなんですけどね。なんかプログラムポシェットの一画面プログラムみたいで(笑)。

で、やってみると…だめ〜。 何が基準になっているかわかりませんが、 1/4ぐらいでもうコンパイルできなくなるのでどうしようもありません。

ということで、 普通の関数にすることにしました(最初からそうしとけって…)。 少々長いので、リンクにしておきましょう。

関数のヘッダファイル:pset.h
関数の実体:pset.c
関数をテストするためのプログラム:psettes.c

2000/09/12
バージョンアップにつき、こちら24-pset01.lzh (3428 bytes)のアーカイブに移動しました。

さて、むちゃむちゃ長かったですが、 なんとか完成したようです。 問題は、実機で試せないことですか(爆)。 まぁMLに放り込んでおけば、どなたか親切な人が試してくれることでしょう。 そんなわけで、今度こそ、次の更新は新サイトで、としたいです。 でわ。

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

第25回PSET for WonderWitch vol.3
実は、前回アップした1時間後にはさらなる高速化に気が付いていたのですが、 さすがにそこまで時間を割くことはできなかったので更新を見送っていました。 で、新サイトでの更新をしようと思っていたのですが、 プロバイダ探しで面白いことになったので更新することにしました(笑)。

いちおう、ひとりよがりなネタでないことを確認すべく、 やねさんに意見を伺ってみたところ、よい反応がかえってきた(笑)ので、 使います。

さて、Webnikが突然のサービス停止を打ち出してから早1ヶ月がたとうとしています。 WebnikからOCNに移行したユーザは12/31まで告知がだせますが、 OCNに移行する気のない僕のページは10/31に閉鎖されてしまう予定でした。 移転の告知は最低でも1ヶ月は出しておきたいので9月中の移転が必要です。 僕自身も忙しい状態なので、かなり急いで新しいプロバイダを探していました。 要するに、切羽詰った状況、です。

いろいろ検討した結果、A社とB社の2社にしぼりました。 ちなみに、A社が移転先予定のプロバイダで、 Ayaインターネットサービスというところです。 B社の名前はいちおう伏せておきます。 間違ってもBで始まる会社ではありませんので、そこ!検索かけない!

残念ながら正確な日付がわからないのですが、 まず、A社のホームページ上から資料請求を行いました。 この時点ではA社にするかは決まっていません。 判断材料が足りなかったので、そのための資料請求です。 2、3日たっても、送られてこないので、 B社と契約することに決め、B社のホームページ上から資料請求を行いました。

ところが、1週間以上たっても送られてきません。 確か1週間半ぐらいだと思いますが。 こんな対応するところは願い下げだと思ったので、 他のプロバイダを探したのですが、どうも条件のあるところが見つかりません。 しょうがないので、A社のホームページで再度資料請求をしました。 30分後、ふと思い立ってA社に知りたい情報を質問するメールを出しました。 これが日曜日のF1が終わった後です。

月曜日、A社からの回答メールが届きました。 それによると、入力フォームのデータ自体が届いていなかったということがわかりました。 知りたかった情報も回答いただき、問題なかったので、そのまま契約するとのメールを送りました。 この契約決定の早さをみても、どれだけ急いでいたかがわかると思います。

さて、B社からの問題のメールが届いたのは、その2時間後でした。 B社および本人を特定できる部分を伏せておきます。 伏字の文字数は適当です。念のため。
 B社の○○と申します.
 資料ご請求の件,大変申しわけございません.
 IP接続サービス対応の関係で,書式が変更となり,ご送付が遅れておりました.
明日発送いたしますので,もう少々お待ちください.
 不手際を重ねて深くおわび申し上げます.

 よろしくお願いいたします.

☆--------------------------------------
 ○○ ○○@B社
  (Marumaru, Marumaru   xxxx, xxxxxxxx, xxxxx)
☆-------------------------------------- 
【営団地下鉄南北線のうた】
 ♪運転手は君だ 車掌も君だ この電車はワンマンだ
最後の2行が問題の件です。プロバイダ探しはかなり急いでいたという背景もあり、 かなり神経を逆なでされた気がしましたので、 資料請求の取り消しを兼ね、次のメールを送りました。 念のため言っておくと、B社のサービスは高く評価していたので、 好意(おせっかいとも言う)をもって指摘したつもりです (僕自身は余計なことに首を突っ込むことを嫌っているのです)。 ちなみに、「さ〜」と書いてあるところは僕の実名が入ってます。
資料請求をした さ〜 です。

>  B社の○○と申します.
>  資料ご請求の件,大変申しわけございません.
>  IP接続サービス対応の関係で,書式が変更となり,
> ご送付が遅れておりました.
> 明日発送いたしますので,もう少々お待ちください.

大変申し訳ないのですが、他プロバイダに申込みを
すませてしまいましたので、資料請求を取り消させて
いただきたいと思います。
発送を取りやめることがお手数でしたらお手間を
かけてまで取りやめる必要はありません。

せっかくのご連絡をいただいたので、
以下に苦言を呈させてもらいます。
気を悪くされるかもしれませんので、
この時点でメールを削除していただいても構いません。
また、このメールの返事をされる必要もありません。


資料請求をした時点では貴社を含め2つの
プロバイダに絞っておりました。どちらかと
言えばほぼB社様に決めており、申込書が
届き次第、契約をするつもりでいました。
しかし、請求をして後、なしのつぶてで
連絡もありませんでしたので、他プロバイダにしました。

1ユーザとして言わせてもらいますと、
何も連絡をせずに1週間以上おいておくということ
自体に、契約後のサポートに不安を感じます。

また、署名の後ろに

> 【営団地下鉄南北線のうた】
>  ♪運転手は君だ 車掌も君だ この電車はワンマンだ

とありましたが、非常にふざけている印象を受けました。
B社様がそのようなくだけたイメージを打ち出している
のであれば、それはそれで構いませんが、少なくとも
私はそのような会社とは契約する気はおきません。

しかし、そのこと以上に、この署名を付けたメールの内容を
考えると、失礼ながら、○○様の神経を疑わざるをえません。
事実、私はこの一文がなければわざわざ時間をかけてまで
このメールを書くことはなかったと思います。

わざわざその理由を説明する必要はないと思いますが、
もし○○様が納得いかないようであれば、お近くの責任ある方に
お尋ねになればよろしいかと存じます。
万が一、問題ないとの回答が得られたのであれば、
クレーマーが自分の価値観で好き勝手言ってやがる、と
思っていただければよいかと思います。

最後になりましたが、B社様の接続状況等を
ホームページ上でこと細かく公開されている点に
ついて、非常に高く評価しています。
また、その他のサービスについても十分以上で
あると感じたことを付け加えさせていただきます。

それでは失礼します。

▼さ〜
    - mailto:asurada@sugo.vip.co.jp
部分的に好戦的にとれる部分もありますが、 このメールはゆうに1時間以上かけて推敲したのですよ。

>また、このメールの返事をされる必要もありません。
は、ひっかけです(笑)。 これだけボロクソ言われているのに謝らない人は救いようがないと思いつつ(変でしょうか?>僕)。 メールを出したのは夜中の2時半だったのですが、 3時半に返事がきました。
 B社の○○です.
 返信不要とのことでしたが,下記お申出の件,まことに申しわけなく深くおわ
び申し上げるため,重ねての失礼となりますが,ご返信申し上げます.

 資料請求のお取り消しについては,確かに承りました.資料の印刷が間に合わ
ないという失態はもちろんのこと,何らの返信も差し上げなかったことについて
ご指摘の通り企業の体制として許されることではなく,以後のお客様対応に必ず
ご意見を役立ててまいります.

 また,シグネチャにつきましても,ご不快の念深くおわび申し上げます.
 以前から技術系のインタネットユーザがよく行ってきたことと認識しておりま
すが,今のインタネットはもっと広い人のものであるということを,身をもって
感じました.

 失礼を重ねておわび申し上げますとともに,末筆ながら大変ありがたいご指摘
を賜りましたことに,厚くお礼申し上げます.

☆--------------------------------------
 ○○ ○○@B社
  (Marumaru, Marumaru xxxxx, xxxxxxxxxx, xxxxxx)

僕の日本語解釈エンジンで、この回答を意訳すると、 「こんなのは普通のことだけど、あんたの価値観が違うから不快にさせてしまったのね。謝るよ」 と読めるのですが。 さらに言えば、せっかくの謝罪がまたこの一文でだいなしになっています(笑)。

僕は、シグネチャの一文が企業のシグネチャにふさわしくない点と、 「申し訳ありません、おわび申し上げます」というメールの末尾に 「♪運転手は君だ 車掌も君だ この電車はワンマンだ」 と付け加える神経を問題にしたつもりなのですが、 巧みに問題がすりかえられてしまいました。

いちおう突っ込んでおくと、 会社のホームページとメールアドレスぐらい書いといたほうがいいと思います。 この話はこれで終わりです。終わりにしました(笑)。

さて、前回をアップしたときにちょうど石田さんから紹介しましたとのメールをいただき、 ページを見にいって、テーブルを使うことを思い出したのです(って、忘れるなよ…)。 ということで、 今回の主題は、

つまり、前回、
buffer[(x&~7) + (y&7) + (y&~7) * SCREENW] |= bit >> (x&7);      
のコードに対して、
インデクスの計算部は…せいぜいテーブルを使うぐらいしかない気がしますね。
とほざいていたのですが、SCREENWは定数なので最適化が可能だった〜、 ということなのです。 ってゆーか、SCREENWって書いたら普通は定数だろ〜。気づけよ〜>僕
を否定することにあります(爆)。

アドレスを計算する部分の元のプログラムを
addr = ((x & ~7) + (y & 7) + (y / 8) * 224 ) *2;
として、どうなるかというと、 最速になるのは、
addr = ( (x & ~7) + y_offset_table[y*2] ) *2;
の場合です。x2は括弧の中に入れても入れなくても今のところ、同じです。 y*2となっているのは、WORDアクセスだからですね。 この方法での問題点はメモリの使用量につきます。 0<=y<144なので、144x2=288byteのテーブルが必要です。 これが大きいか小さいかは場合によりますが、 このテーブルを小さくした場合を考えてみます。

一番スタンダードと思われるのは、y/8をインデクスにする場合です。 この場合、要素数は144/8=18なので、テーブルサイズは36byteです。 このプログラムは、
a = y;
a >>= 2;
a &= ~1;
a = y_offset_table2[a];
y &= 7;
addr = ((x & ~7) + a + y) *2;
こうなります。 こいつは、テーブルの中身をちょっと工夫すると、
a = y;
a >>= 2;
a &= ~1;
a = y_offset_table3[a];
addr = ((x & ~7) + a + y) *2;
とすることができます。どうすればいいかわかりますか? もとのテーブルは、
WORD y_offset_table2[] = {
	28*8, 28*16, 28*24, 28*32, 28*40, ....
 };
こうですが、
WORD y_offset_table3[] = {
	27*8, 27*16, 27*24, 27*32, 27*40, ....
 };
こうすればいいわけです。 最後にyを加えるときに1倍を加えて28倍を作るわけですね。

さて、次はテーブルサイズを2倍にしましょう。
a = y;
a >>= 1;
a &= ~1;
a = y_offset_table4[a];
addr = ((x & ~7) + a + y) *2;
シフト量が1減ったので、1クロック減、サイズ倍です。

さらに倍にしてみましょう。
a = y;
a &= ~1;
a = y_offset_table5[a];
addr = ((x & ~7) + a + y) *2;
さらに1クロック減、サイズ倍ですね。

アセンブラで書いてみた場合のクロックを表を示します。

表1:テーブルサイズとアドレス計算に必要なクロック
テーブルサイズクロック(概算)
18x2byte9
36x2byte8
72x2byte7
144x2byte5


う〜ん、違うような、違わないような…。 ま、これは使う人が選択すべき問題なので、 defineで切り替えるようにすればいいでしょう。 グラフィックライブラリを作る場合は、 迷わず144x2byteを使用して、他のルーチンでも共通して使用すべきだとは思いますが。

さて、実はもう一つ、高速化できる場所がありました。 この高速化を行うことで、 色1,2のときは1クロック増ですが、 色3のときに6クロック減とすることができます。 ということは、同確率であると仮定すると、
(0+1+1-6)/4=-1
1クロック減です。あんま変わらんな…、こりゃ。

それでは、問題の部分を抜き出して。
	/* 書き込む値の計算 */
	or  cx, cx
	jz  _skip_calc

	/* 書き込む色が0でない場合 */
	add cx, 00feh
	and cx, 0101h
	add cx, 7f7fh
	xor cx, 8080h
	and bx, cx

 _skip_calc:
	xor ax, bx
	mov es:[di], ax
ここで注目すべきなのは、cx==3のときは、axの値を加工せずに書き込める点です。 つまり、
	/* 書き込む値の計算 */
	or  cx, cx
	jz  _skip_calc
	cmp cx, 3
	jz  _skip_calc2

	/* 書き込む色が0でない場合 */
	add cx, 00feh
	and cx, 0101h
	add cx, 7f7fh
	xor cx, 8080h
	and bx, cx

 _skip_calc:
	xor ax, bx
 _skip_calc2:
	mov es:[di], ax
とできるわけですね。 ここで、cmpは必要ないというところが今回のウリです。 こうしてしまいましょう。
	/* 書き込む値の計算 */
	and cx, 3
	jz  _skip_calc
	jpe _skip_calc2

	/* 書き込む色が0でない場合 */
	add cx, 00feh
	and cx, 0101h
	add cx, 7f7fh
	xor cx, 8080h
	and bx, cx

 _skip_calc:
	xor ax, bx
 _skip_calc2:
	mov es:[di], ax
これでOKです。and cx,3を実行したときに、 cx==0の場合は、ゼロフラグが立ちますので、 次のjzでジャンプすることができます。

cx==3の場合は、and cx,3を実行したときに、 パリティフラグが立ちます。このフラグは、 演算結果の値において、1のビットが偶数のときに立ちます。 つまり、cx==0とcx==3の場合に立つわけですが、 cx==0の場合はすでにジャンプ済みなので、 jpeでジャンプするのはcx==3の場合であるというわけです。

最後におまけで、8byte小さくします。問題のコードは、 x座標からマスクデータを取得する部分です。
dx : maskを入れるレジスタ
ax : x座標

mov di, ax
and di, 7
add di, di
mov dx, cs:[di +mask_data]
こいつを
dx : maskを入れるレジスタ
ax : x座標

mov di, ax
and di, 7
mov dl, cs:[di +mask_data]
mov dh, dl
こうします。 つまり、上位と下位の内容が同じなので、コピーですませるわけです。 これでテーブルサイズは半分になります。 実行クロック数は同じ(はず)です。

修正を加えたコードをファイル名同じでアップしておきます。 ちゃんと昔のコードも入ってますが、 昔のバージョンのアーカイブをこちらに用意しておきます。

関数のヘッダファイル:25-pset.h (2322 bytes)
関数の実体:25-pset.c (5493 bytes)
関数をテストするためのプログラム(変更なし):25-psettes.c (1504 bytes)

これでほぼ終了だと思います。いや、まぁ、いつもそう思っていながら、 後で気が付くのですが。このコードでやり残していることは、 間接参照時のアドレス生成時のストール回避で、 こいつは命令を入れかえれば簡単に回避できます。 コードが読みにくくなるので行っていませんが。 このコードを使う方はトライしてみてください。

さて、いかがでしたでしょうか。 予想外の出来事がありましたので、急遽3時間で文章を書き上げましたので、 説明が抜けている部分もあるかもしれません。 そんときは、ご指摘くだされば必要な範囲での補足をしたいと思います。 実際、最後の読みなおしをしてみると、 むちゃむちゃ説明を急いでいる感を受けました(笑)。 ま、いいやー

これからA社に契約金を振込みに行くので、 次こそは新サイトでの更新となる、はずです。 今日明日の更新がなければ〜ですね(笑)。 すぐに使えるようになるはずなので、 なにかあっても数日ぐらいは更新を我慢するつもりです(^^;

新サイト移転後の予定としては、 参考文献のリンクを作ろうと思ってます。 自分のために(笑)。 それでわ。

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

第26回無圧縮PNGの怪
はじめに

さて、なんとなく、移転し始めたような、そうでないような移転状況ですが、 これにはわけがあります。 ってゆーか、 ふざけんな〜な感じです。 僕は、GIFが嫌いです。そして、PNGが好きです。 何故かと聞かれると返答に困りますので、 それはともかく。

サイト移転ということですが、 困ったことに用意されているCGIはせいぜいカウンタぐらいです。 ということは、 Webnikでサポートされていたフォーム送信関係を移行するために、 自分でなんとかする必要があるってことです。

ということで、いろいろCGIを探しましたが、 PNGのカウンタが見つかりません(笑)。 ということで、サクッと作ろうと思い立ったの無理からぬことでしょう。 当然、画像結合もできなければ、GIFに負けてしまいます。

そんなこんなで、PNGカウンタ作成に着手しました。 といっても、Perlはまだ触ったことがないので(笑)、 いきなり画像を解析して、というつもりは毛頭ありません。 せいぜい、現在のいけてる率の表示ぐらいできればいいだろう、程度です。

PNGフォーマット概要

さて、PNGのフォーマットですが、 忘れた頃に役にたつCマガに載っていました(1998年6月号)。 これを読むとかなりのところまではわかります。 PNGフォーマットは、最初にPNGシグネチャがあり、その後ろにチャンクがずらずらと並びます。 情報は、必要に応じてチャンクとして記述するようになっています。

PNGフォーマットの構造
図1:PNGフォーマットの構造

IHDRとIENDにはさまれたIDATが画像になるとかなんとか決まっているようですが、 とりあえず表示するために、最低限のチャンクだけ使った図2の構造だけを考えることにします。 他のチャンクを扱いたい人は独自にどうぞ(^^;

最低限のPNGフォーマット
図2:最低限のPNGフォーマット

PNGシグネチャ

さて、PNGシグネチャの詳細です。 こいつは簡単になっており、テキストで見れるようになっているのですが、 先頭の(C)が日本語フォントで見たときに文字化けするあたり、 欧米人の自己中心的な感じを受けます(笑)。 そのデータ列を図3に示します。

PNGシグネチャのデータ列
図3:PNGシグネチャのデータ列

チャンクのデータ構造

さて、ここから少しずつわかりにくくなってきます。 チャンクのデータ構造は図4のようになっています。 データ長、CRCはunsignedで4byteのサイズで、 上位が先にくるビッグエンディアン(ネットワークエンディアンと呼ぶらしい)で保存されます。 これがやらしいところです。



チャンクの構造
図4:チャンクの構造

IEND

さて、個々のチャンクデータについて説明します。 まずは一番簡単なIENDです。 こいつは、ただの目印のようなもので、 チャンクデータサイズは0です。 CRCはチャンクタイプとチャンクデータで計算しますが、 チャンクデータがないということは、CRCがチャンクタイプに依存しているということで、 要するに、固定です。 1回計算して(計算しないで丸写しでもいいですが)、得られた値をそのまま書きこんでいいんじゃないでしょうか。 図5のようになります。



IENDの構造
図5:IENDの構造

IHDR

さて、次に簡単なのはIHDRチャンクです。 画像に関する情報を保持するために、データチャンクがちゃんく存在します (つまらなすぎ…)。 幅と高さが4バイトずつです。この値はビッグエンディアンで格納するのを忘れずに。 色深度とカラータイプは表にしたがって設定します。 圧縮方法とフィルタリング方法は、現在のところ、0しか許されません。 インターレース方法も簡単のために、ここでは0にしておきます。 図6に、幅1高さ1、24bppの画像のヘッダを示します。

IHDRの構造
図6:IHDRの構造

IDAT

さて、一番の難関、IDATです。 理解してしまえば、別にどうということもありませんが、 とにかくドキュメントに記述がほとんどないので、 そこがきついです。ソースコードで理解しようにも、 pnglibでは全く触れていませんし、zlibでは、それはもうぐちゃぐちゃに書いてあります。 あ、僕から見て、ですが。

データとしては、 圧縮してあろうが、無圧縮であろうが、図7の構造になっています。 この構造を理解するまで結構かかりました。なにしろはっきりしないもので。



IDATの構造
図7:IDATの構造

このように書いてしまえば、IDATが難しいのではなく、 実はDeflate圧縮データが面倒だということがすぐにわかります。

Deflate圧縮データ

さて、もっともわけがわからなかったDeflate圧縮データの解説です。 データ構造としては、図8のようになっています。



Deflate圧縮データの構造
図8:Deflate圧縮データの構造

それぞれのデータフィールドは次のような意味を持っています。

CMFとFLGは特に変更する必要もないので、固定値として扱ってしまってもいいでしょう。 ちなみに、ソフトによってFLEVELが違うので、プログラマのプライドをそこに見ることができます(笑)。

無圧縮 COMPRESSED DATA

さて、無圧縮なのにCOMPRESSEDとはこれいかに。それはともかく、 どんどん話が限定されつつあります。 COMPRESSEDデータは、複数の(もしくは一つの) COMPRESSEDブロックから構成されます。 無圧縮の時のCOMPRESSEDブロックの構造を図9に示します。



無圧縮 COMPRESSED BLOCKの構造
図9:無圧縮 COMPRESSED BLOCKの構造

最初の1バイトのbit3〜bit7は読み飛ばされます。

LITERAL DATA の中身

さて、ようやく最後にたどりつきました。LITERAL DATAの中身はなにかというと、 PNGにおけるスキャンラインの集まりです。 図8のSCANLINE DATAにあたります。 PNGはスキャンラインごとにフィルタを指定できるようにするため、 データ構造は図10のようになっています。



PNGのスキャンラインデータ
図10:PNGのスキャンラインデータ

FILTERには、IHDRで指定したフィルタセットの中から自由にフィルタを選択して設定できます。 ここでは、無圧縮ということで、NONE=0 にしましょう。 これで無圧縮PNGフォーマットについてすべての説明が終わりました。 あとはプログラムを作ればいいだけです。

PNGの実装法

さて、実際にプログラムを組むために情報を集めるべく、 検索サイトで、「PNG」といくつかのキーで検索をかけると、 結構な数のプログラムを見つけることができます。 しかし、だいぶ見て回りましたが、libpng+zlibを使わないで実装しているのは、 見つけることができませんでした。 確かに、libpng・zlibはライブラリとして完成されたものであるだけに、 プログラムする人も符号化部は触りたくないのでしょう。

でも、たかだか無圧縮のPNGを吐き出すのに、 わざわざライブラリを2つも使うのはしゃくです。 なにより、それではPerlでCGI化が困難です(笑)。

ということで作ってみました。 で、InternetExplolerに突っ込んで見ると…あ、落ちた(笑)。

おっかしーなー、どこが違うんだろーとバイナリとにらめっこを続けること数時間。 結局、わかんねーということで、pngcheckerなるプログラムを検索。 PNGフォーマットとしておかしいんかなーということですな。 で、いくつか見つけて試してみたのですが、吐き出したPNGは問題なしとの診断。 なぜだー。わからーん。

libpng.libの探索

さて、それならばしょうがない、ということで、 ライブラリコードを追うことで、どこに問題があるかを探すことにします。 グラフィックソフトやブラウザ等では、標準出力がなく解析しにくいので、 コンバータを探しました。当然、ソースコードつきのを。

検索した結果、 宮坂さんのページにBMPとPNGのコンバートをするプログラムを発見しました。 これを使えば、コマンドラインから実行できるので、標準出力にコメントを出力すれば画面に表示できます。 使うファイルは、PNG2BMP.Cのほうです。これでBMPに変換する際にデコーダとして、 libpngとzlibが呼び出されるわけです。

試しに変換してみたところ,
Not enough image data
と表示されました。

それでは探索してみましょう。 PNG2BMP.CでPNGデータを展開する部分は次の行です。
	png_read_image( png_ptr, img->rowptr );

ということは、やはりlibpng内を読まなければなりません。 どこ見るべきかというと、 pngread.cです。

png_read_image( )を見ると、 各ラインごとにpng_read_row( )を呼び出しています。 ぐちゃぐちゃしてて非常にわかりにくいですが、 流れとしては難しくありません。 肝心のデコード部分は、 最後のブロック以外を読み出すdo-whileと、 最後のブロックを読み出す png_read_finish_row( ) がくっついているだけです。

puts( )をいろいろ置いたり考えたりした結果、 原因がわかってきました。問題の部分は、最後のブロック以外を読み出すdo-while内の

    do { ...
      ret = inflate(&png_ptr->zstream, Z_PARTIAL_FLUSH);
      if (ret == Z_STREAM_END)
         ... break;
    } while( );

です。 この部分が何をしているかというと、inflate( )で現在のブロックを展開します。 このとき、BFINALが1であれば、戻り値が Z_STREAM_END として返ってくるので、 ループから外に出て、png_read_finish_row( ) で仕上げを行うのです。

ところが、僕のプログラムで吐き出した無圧縮PNGファイルでは、 Z_STREAM_ENDが戻ってきていないので、エラーが出る、という寸法です。

zlib.libの探索

さて、問題の inflate( ) の動作ですが、 この関数がどこにあるかというと、zlib内にあるのでした。ひぇ〜。 結局は、libpngも、PNGの圧縮に関してはzlibに丸投げしているわけです。

inflate( ) は、zlibのソースの inflate.c にあります。 関数内を見ると、状態遷移のswitch文がぼかっと置いてあります。

  while (1) switch (z->state->mode)
  {
    case METHOD:
    ...

初期状態がわからないので、各ケース文がどの順番で呼び出されるかを調べてみます。

   case METHOD:
   case FLAG:
   case BLOCK:

の順番で処理されていました。 case BLOCK:では、ブロックの展開をしているようです。

      r = inflate_blocks(z->state->blocks, z, r);
      if (r == Z_DATA_ERROR)

inflate_blocks( )の戻り値をチェックすると、特にエラーが返ってきてるわけではありませんでした。 そのかわりといってはなんですが、 ブロックはすべて展開したはずなのに、

      if (r != Z_STREAM_END)
        return r;

の条件が成立していないようです。 ということは、inflate_blocks( ) を読まねばならないようです。

inflate_blocks( ) は、infblock.c にありました。

  while (1) switch (s->mode)
  {
    case TYPE:

inflate( ) と同様になっています。やはり初期状態がわかりませんが、 呼び出しの順番は調べるまでもありません。 最初にチェックするのは、圧縮タイプでしょう。 case TYPE:の処理をチェックすると、 正常に無圧縮として認識しています。

無圧縮として認識されると、次はcase LENS:に処理が移ります。 そこでは、b にLEN+NLENを読み込み、チェックをして、 s->sub.leftに長さを放りこみます。 そして、状態をSTOREDにして終了です。

case STORED:を見ると、 s->sub.leftの長さをチェックした上で、Compressed Dataから展開先のバッファにコピーしています。

原因の特定

さて、ざっと見たところ、プログラムの不備は当然ありませんし、 プログラムの動作に照らし合わせてもデータ自体の間違いもなさそうです。 では、どこが原因なのでしょうか。

プログラムの流れ自体に問題がなければ、そこを流れるデータがおかしいはずです。 試しに、無圧縮データの長さが格納されている s->sub.left を表示してみます。

 s->sub.left = 0x400

え…?変です…。今は幅1dotのPNGを作成しているので、 無圧縮データの長さは、
FILTER(1byte) + WIDTH(1dot) x RGB(3byte)=4byte
のはずです。 バイナリエディタで作ったPNGファイルを見ても、LENとNLENは

00-04-FF-FB
となっています。s->sub.leftに代入する値は、

    case LENS:
      NEEDBITS(32)
      if ((((~b) >> 16) & 0xffff) != (b & 0xffff))
      {
        s->mode = BAD;
        z->msg = (char*)"invalid stored block lengths";
        r = Z_DATA_ERROR;
        LEAVE
      }
      s->sub.left = (uInt)b & 0xffff;

となっていますから、bに入っているはずです。 LEN==~NLENのチェックはエラーがでていないのが謎ですが…。 それでは、NEEDBITS(32)の次の行で、bの値を表示してみましょう。

b = 0xFBFF0400

は?おかしいです。これではリトルエンディアンで読み込んでいます。 バグちゃうんかー、これ〜

試しに、PNGファイルをバイナリエディタでいじくってみます(笑)。
修正前:00-04-FF-FB
修正後:04-00-FB-FF
で、こいつを食わせて見ると…うわ、変換しやがった(爆)。 さらに、そこらのアプリに突っ込んで見ましょう。 うゎ、動いてやがる(笑)。

えーっと…どうしよう…。 おかしいなぁ…、zlibの方はリトルエンディアンなんかなー? RFC1950にはネットワークエンディアンって書いてあったのに、 違うのかなー? zlibの詳細はRFC1951か…

…あれ?いけてねぇ〜

RFC1950: ZLIB Compressed Data Format Specification version 3.3
             0     1
         +--------+--------+
         |00000010|00001000|
         +--------+--------+
          ^        ^
          |        |
          |        + less significant byte = 8
          + more significant byte = 2 x 256

RFC1951: DEFLATE Compressed Data Format Specification version 1.3 0 1 +--------+--------+ |00001000|00000010| +--------+--------+ ^ ^ | | | + more significant byte = 2 x 256 + less significant byte = 8

なんだよ、これ〜、やっとれんわー。 ってゆーか、わかるかー。 あーぁ、いろんな人にバグだバグだと言っちゃったよ(笑)。 ま、いいか。

おわりに

さて、しょーもない結末に落ち着きましたが、 これで心置きなくPNGカウンタの作成ができます(笑)。 だってよー、もしzlibがバグってたとしたら、 使えんでしょ、アプリ落ちちゃうし。 いや、落ちたアプリはIEだけだけど(笑)。

それはそれとして、 無圧縮PNGについて解説したページは全く見つからなかったので、 前半だけは資料価値があると思うのですが、だめ?

あー疲れた、でわ。

参考文献

付録

2000/10/02追加 64KByte以内に限定したBMP→無圧縮PNGコンバータ26-png.cpp (4465 bytes)。 入力ファイル名はinput.bmpに固定になっているのはおまけだから。

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

第27回固定小数点における遅くはない乗算
いつものイントロ

冗談で言ったら、あれよあれよという間に、 周りの人が乗り気になってしまった、やね講演会ですが、 もう面倒なんですよ。 学祭委員が招待しているわけではないので、 学祭委員とやねさんが直接打ち合わせをするということはできません。 で、やねさんに対しては僕が連絡役になるわけですが、 僕が学祭委員と連絡しているかというとそうではないんですよ。 MCCというサークルの招待ということで、 MCCの部員が学祭委員と打ち合わせをして、その後、 僕を通してやねさんに伝わるわけです。

そんなこんなでパイプ役をしていると、 面倒ですよ〜。まぁ、楽しみしている方も多いようなので、 それが活力の源ですか。 いや、そんなことを言いたいんではないんですよ。 こんだけ間に入る人が多いと、 それだけ情報のやり取りに時間がかかるってことなんです。 仮にやねさんが質問したとして、学祭委員が応答に同じだけの時間をかけるとすれば、 MCC部員と僕に連絡を通す時間だけ余分にかかるってことです。 極限の応答を求める場合には、 このオーバーヘッドは避けておくのが無難です。

避けられないオーバーヘッド

しかし、場合によってはオーバーヘッドを避けることができないこともあります。 Windowsプログラミングで言えば、APIです。 APIは、その名称の通り、Application Programming Interfaceということで、 インタフェースの先を変更することは叶わないわけです。 ということは、いくら
この関数は、各Win32プラットフォームに合わせて最適化されています。
と書いてあったところで、 インタフェースの先のコードをインライン展開したコードよりは確実に遅いわけです。 インタフェースの先がインライン展開されれば同じにはなるはずですが、 そのようなことはありえません。 したがって、DLL内部の関数を呼び出した場合には、 必ずDLL内部のコードが実行されている(はず)です。 確認してませんけど。

高速な固定小数点演算

さて、なんでこんな話をするかというと、 やねさんのページを見て、 MulDivという関数を知ったからなのです。 この関数、32bit整数同士を掛けた後、結果の64bit整数を別の32bit整数で割るという動作をします。 こいつで、
c = MulDiv(a, b, (1<<16));
とすると、第22+回で作成した Mul( ) マクロと同じことができます。 ということで、僕のしたことは意味なかったんか〜と思っていたのですが、 関数呼び出しのオーバーヘッドとAPI呼び出しのオーバーヘッドを考えると、 Mul( )マクロのほうが高速なはずです。

でわ、実験。

プログラムはこんな27-mul.cpp (690 bytes)感じになってます。 試行回数1000万回にしてみました。
#include "stdio.h"
#include "windows.h"
#pragma comment(lib, "winmm.lib")
#define MUL(c, a, b)		{	\
	DWORD tempA = a;			\
	DWORD tempB = b;			\
	__asm {						\
		__asm mov  eax, tempA	\
		__asm mov  edx, tempB	\
		__asm mul  edx			\
		__asm shr  eax, 16		\
		__asm shl  edx, 16		\
		__asm or   eax, edx		\
		__asm mov  c,   eax		\
	} }
#define ESTIMATE		10000000
 
void main(void)
 {
	DWORD tm[3], a, b, c;
	int i;
	a = 100;
	b = 200;
 
	tm[0] = timeGetTime( );
 
	for(i = 0; i < ESTIMATE; i ++)
		MUL(c, a, b);
 
	tm[1] = timeGetTime( );
 
	for(i = 0; i < ESTIMATE; i ++)
		c = MulDiv(a, b, (1<<16));
 
	tm[2] = timeGetTime( );
 
	printf("%d , %d\n", tm[1] - tm[0], tm[2] -tm[1]);
 
 }
で、その結果。


Table1 MulマクロとMulDiv関数の比較

MulマクロMulDiv
306 (msec)2170 (msec)

試行回数がかなり多いのは置いといて、無駄な苦労ではなかったようです。 あぁ、よかった。 それにしても、こんな短いのも久しぶりだなぁ(笑)

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

第28回C++で始めるお手軽オブジェクト指向
いつものイントロ

いや、決してまともだと思っていたわけではないのですが、 ここのところの森首相、以前にもまして分別の無い発言ですね。 神の国発言やらなんやらはリップサービスの度が過ぎたなどと、かばえたのですが、 さすがに行方不明第三国発見に関しては、どなたもそのようなことはおっしゃれないようで。

一応、説明しておきますと、 北朝鮮拉致疑惑に関して、拉致された人を第三国で発見されたことにすれば、 北朝鮮は拉致したことを認めなくともよく、日本は拉致された人を取り戻すことができるって案だったのです。 報道を見ると、どうやらこの方向で調整が進められていたようなのですが、 あろうことか森首相が第三国の首相に自慢気に明かしたために、 世間に広まってしまったということなのです。 どうも、森という方はどの情報が公開していいか、 ということはまったく理解できないようで、 こういう人が政治家という職業についていても不安を感じないのは自民党を応援する方々なのでしょうなぁ。

今日のお題

このように、公開してはならない情報を世間に知らしめる可能性のある場所に置くのは、 森を首相にしておくぐらい危険なわけです(笑)。 ということを念頭に置くと、 クラスのprivateメンバをヘッダファイルに書くということのアホさが理解できると思います。

オブジェクト指向を勉強するのにC++は最悪な言語であるとは、 C++の入門書でよく見かけますが、この1点をとってみても僕にとっては十分なのです。 というか、おりゃ〜とプログラムを作っていて、 一番頭にくるのがこの点なのです。 オブジェクトをクラスとして実装した場合には、 外部からはクラスインタフェースが重要なのであって、privateメンバなぞまったく興味がないわけです。 ところが、C++ではprivateメンバとpublicメンバをすべて同じところに書かねばならなく、 それだけで鬱陶しいを通り越して、切れそうなのです(笑)。

腐った例

その他にも腐る原因はあります。 例えば、クラスAがあったとき、このクラスA内でだけ使用する構造体Sがあるとします。 この構造体は、クラスAで閉じているわけです。 このとき、普通に書こうとすると、
struct S { int m; }
class A {
 private:
    struct S ms;
 };
こうなるわけです。クラスの内部でしか使わないのに!。 もし、インタフェース定義と内部定義を別の場所に書くことができれば、 こんな間が抜けたことはしなくて済むのです。

プリプロセッサによる解決

このようなC++の仕様による問題を根本的に解決する方法は、 新しい言語を作ることなのでしょうが、 そんな時間も能力も経済力もないので、 せいぜいプリプロセッサを作るぐらいが関の山です。

だいぶ前になりますが、C言語で日本語のラベルを使えるようにするため、 日本語のラベルを英文字のラベルに置換するプログラムを作ったことがあります。 このとき、エラー表示がわかりにくくなるという問題点がありました。 置換の対応は指定できるようにしてあったのですが、 いちいち日本語ラベルと英文字ラベルの対応をセットしておくのは面倒なので、 自動割当てすることになるわけです。 で、その結果、エラー表示は英文字のラベルですから、 わけがわから〜ん、ということになりました(笑)。

このように(?)、プリプロセッサは確かにお手軽ですが、 実際の使用となると、コンパイラのエラー表示が対応しないため、 開発時に面倒になるはずです。 ってゆーか、なりました(笑)

従来の手法

とかなんとか好き勝手言っていると、C++をこよなく愛する方に、 「そういう場合は、インタフェースクラスを用意して、 それを継承するのだー」としかられてしまいます。 具体的には、こんな感じになると思います。

確かに、C++の実装上はこうするのが妥当であることはわかりますが、 プログラムを組む上で、一つのクラスを作るたびに、 一つのインタフェースクラスを作って…というのはいかにも間が抜けています。 さすがにそこまで徹底している方はいないと思うのです。

似たような意味を持つ手法として、関数群でラッピングする方法もあります。 これは、Windowsの真似ですが、
class A {
 public:
	A( );
	~A( );
	method( );
 };

とあったら、
class A *CreateA( );
method(class A *a, ...);
Delete(class A *a);
とか関数を作って、こちらだけ公開する方法です。 第一引数にクラス定義を使うために、 method名が重なっても関数の多重定義として扱われるのでそれなりに賢い方法かも、です。 ただ、オペレータの定義が使えないので、 クラスの替わりには使えません。

ほかにも、
void *mps;
とか定義しておいて、実装の方で、
mps = new struct S;
と確保した上で、
(*(struct S*)mps).m = 1;
としてアクセスする方法もありますが、 そのような人はそっとしておきましょう(笑)。

提案する手法

さて、インタフェースクラスを作る手法は、 オブジェクトの切り分けが確定した後であれば、 できないことはありません。しかし、設計に見切りをつけてスタートした場合、 インタフェースもごそっと変更〜ということがあるので、 いちいち継承なぞしてられんのです。 ということで、なんとかならんもんかな〜とずっと考えていたのですが、 とうとう思いつきました。

クラス定義のところに直接実装を書いてしまうことにするのです。 こんな感じになります。


class A {
	#include "A.class"	// javaっぽく。
 public:
	method( );
 };

これですっきりするのですが、残念ながら、 method( )定義をA.class内に書くことができないので、
method( ) { return _method( ); }
などとして逃げざるを得ないかもしれません。

この手法の欠点は分割コンパイルできないところですが、 内部メンバだけをA.classに書くことにして、 実装を.cppに書くことにすれば、ファイル数は増えますが分割コンパイルには対応できます (無理やりだな〜)。 長所としては、 A.class内に間違いがあった時のコンパイラの表示が正しいことでしょう。 VisualC++6.0で確認しました。

ちなみに、この方法、publicメソッドをprivateメソッドに振り替えると、 インタフェースクラスを作るのとほとんど一緒だったりします。 書く人が、どちらが楽か、という程度で。 一応、inline展開できるので、 関数定義をたどる分だけ有利とは言えますが、 そんなに影響するほどとは思えません。

ただ、この手法ならば、C++初心者でも悩むことはありません。 ふつーに書けると思います。 え?僕は使ってるのかって? 気が向いたら使ってみることにしますね。

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

第29回真・C++で始めるお手軽オブジェクト指向
いつものイントロ

後輩から

「さ〜さん、ホームページ更新してんですかー」

と聞かれたので、

「してるよー」

と言いつつブラウザにアドレスを入力。 どうやら彼は"オブジェクト指向"の文字列に反応したようです。

「お、じゃぁ読まなきゃー」

しかーし、そ、その回は…

「役に立たないよー。その回、実際にプログラム書いたら全然意味無かったんだよね。 フォローしたいんだけど、書く暇ないんだよなー」

「だめじゃん。ちゃんとフォローしないとー」

ということで渋々フォローを書き始めたのでありました。

親切な人の指摘

それはともかく、匿名の方から前回提案した記述法の問題点を指摘されました。

  • インライン展開されるので実行ファイルがバカでかくなる
  • 循環参照を解決できない

インライン展開については、言われてみればそのとおり、 書いたときは忘れてました(笑)。 循環参照の問題は、気がついてましたが、 お手軽ということで、ま、いっか。と流してました。 これらの欠点はまさにその通りなのですが、 それ以前の問題があったりなんかして、その問題に比べれば別にたいした問題ではない、 ような気がします。

実際のプログラム

前回提案した方法を使って、スライド辞書圧縮のプログラムをクラス化してみました。 圧縮に使用するバッファを外部で用意する必要があるのは、 まぁ、ある用途に実際に使うためなので、目をつぶってちょーだいよ。 実際のプログラムはこちら29-slide.lzh (2291 bytes)。 試すときは、640x480x256のtest.bmpを用意してくださいね。


/ slide.h #ifndef SLIDE_HEADER #define SLIDE_HEADER #include <windows.h> class CSlide { #include "slide.class" public: int Decode(BYTE *dstBuf, int dstSize, BYTE *srcBuf, int srcSize) { return _Decode(dstBuf, dstSize, srcBuf, srcSize); } // 圧縮。戻り値は圧縮後のサイズ。-1ならエラー(バッファが足りない) int Encode(BYTE *dstBuf, int dstSize, BYTE *srcBuf, int srcSize) { return _Encode(dstBuf, dstSize, srcBuf, srcSize); } }; #endif // SLIDE_HEADER

slide.classファイルを示すことはしませんが、 これを見ればわかるとおり、 publicな関数からprivateな関数に振り替えるため、 それをいちいち書かねばなりません。 これって…、かっこわる〜。

publicの定義をどうにか1回ですませられないかなぁ〜といろいろ考えて、 public定義をslide.classに移動して、ヘッダにはそのプロトタイプを書いて… こんな感じかなぁ。

class CSlide
 {
	#include "slide.class"
 public:
	// int Decode(BYTE *dstBuf, int dstSize, BYTE *srcBuf, int srcSize);
	// int Encode(BYTE *dstBuf, int dstSize, BYTE *srcBuf, int srcSize);
 };

…あれ?こ、これって…。 単にインターフェイスをドキュメントに書くのと同じなんじゃ…。 意味ねぇ〜(笑)

でも、ファイルが増えていいなら少しはましになりますかね。

---- slide.h ----
class CSlide
 {
	#include "slide.class"
 public:
	int Decode(BYTE *dstBuf, int dstSize, BYTE *srcBuf, int srcSize);
	int Encode(BYTE *dstBuf, int dstSize, BYTE *srcBuf, int srcSize);
 };
 
---- slide.class ----
private:
BYTE text[N+F-1];		// テキスト用バッファ
void InitTree(void)
 {
	for(int i = N +1; i <= N +256; i ++)
 ...以下略
 
---- slide.cpp ----
int CSlide::Decode(BYTE *dstBuf, int dstSize, BYTE *srcBuf, int srcSize)
 { return _Decode(dstBuf, dstSize, srcBuf, srcSize); }
int CSlide::Eecode(BYTE *dstBuf, int dstSize, BYTE *srcBuf, int srcSize)
 { return _Eecode(dstBuf, dstSize, srcBuf, srcSize); }

しかし、これだとslide.classファイルの存在意義が薄くなりますね。 いっそのこと、関数の実態はslide.cppに移動して、 slide.memberとかいうファイル名にしてしまうとか。う〜ん、うざったい…。

新手法の提案

と、ここまで書いていてなんですが、 これらの問題をすべて解消する記述法を思いつきました。 こいつはかなり理想的っぽいです。 とかなんとか言っちゃって、実際に使ったら使えねぇ〜とならなきゃいいのですが(笑)。

---- slide.h ------------------------
#ifndef SLIDE_HEADER
#define SLIDE_HEADER
 
class CSlide {
	#include "slide.cpp"
 public:
	void method(void);
 };
#endif
 
---- slide.cpp ----------------------
#include "slide.h"
 
#ifndef SLIDE_METHOD
 private:
	メンバをここに書く。
#define SLIDE_METHOD
#else
 

/ ここには普通に実装を書く。 void CSlide::method(void) { } #endif

おお、なかなか。先ほどのスライド辞書圧縮クラスを実際に書きなおしてみました。 こちら29-slide2.lzh (2325 bytes)です。 使い方はまったく同じです。

ヘッダファイルからcppファイルをインクルードするという、 気持ちの悪いところがあるとはいえ、いい感じだと思いますが。 少なくとも、.classなどというわけのわからない形式のファイルがあるよりはいいでしょう(笑) もう一つの利点としては、メンバ定義と実装が一つのファイルに納まっているので、 編集しやすい、です(少なくとも僕はそうです)。

複数のクラスを含む場合の考察

さて、書き終わったと思っていたのですが、 よくよく考えてみると、ヘッダファイルに複数のクラスが定義されており、 かつ、cppにその実装が書いてあるとするとちょっと考えなければなりません。 どのようにすれば問題が起きないでしょうか。

ヘッダにクラスを記述した順番どおりにcppファイルに記述することにするのであれば、 大きな変更は必要ありません。でもねー、それはいかんでしょ。 もし、ヘッダでの定義順と、cppファイルでの順番を間違えると、 ひどいことになることは目に見えてます。

ということで、多少汚くはなりますが、このように記述することにします。

---- class.h ------------------------
#ifndef SLIDE_HEADER
#define SLIDE_HEADER
 
#define CLASS_A
class CclassA {
	#include "class.cpp"
 public:
 };
 
#define CLASS_B
class CclassB {
	#include "class.cpp"
 public:
 };
 
#endif
 
---- class.cpp ----------------------
#include "slide.h"
 
#ifdef CLASS_A
 private:
	CclassAのメンバをここに書く。
	#undef CLASS_A
#elif defined CLASS_B
 private:
	CclassAのメンバをここに書く。
	#undef CLASS_B
#else

/ ここには普通に実装を書く。 void CclassA::method(void) { } void CclassB::method(void) { } #endif

#elifdefがないので、#elif definedと長くなりますが、まぁしょうがないでしょうなぁ。 それぞれのブロック内で#undefしているのが苦労のあとです(笑)。 これでだいたいの問題は回避できると思いますが、どんなもんでしょうか。 ぎゃるぱにXも、今から追加するクラスはこう書きなおしてみますかねぇ。 とくに問題が生じそうな気配もなさそうですし。

感想お待ちしてますねん。でわ。

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

第30回色抜き転送 for WonderWitch
いつものイントロ

みなさん、ざわざわ〜。30回ということで雰囲気を変えようかと思いまして、 その結果がざわざわです。わけわかりませんね。 そんなことをしている間に年が明けてしまいました。 といっても、僕にとってはただの週末、 あ、違うな、ただのコミケのある週末でした(笑)。

昨年、ある同人CG集を通販で申し込み、振込みまですませたのですが、 一向に送られてきません。本人にとっては不名誉なことで、 当然了解もとってませんのでどこの誰かは秘密なのですが、 仮にAさんと呼ぶことにします。 例によって例のごとく、Aは名前の頭文字とは一切関係無いので、 リンク集で探したりしても無駄です。

さて、通販で同人CG集を買うのは全くもって始めてでしたので、 振込んで1ヶ月ほどたってころに不安になりました。 さらに言えば、見たいからCG集を買ったわけで、早く見たいのです。 で、振込みを確認できたかどうかの問い合わせと併せて、 なにか問題があったかをメールでたずねてみることにしました。

僕がメールを出してから数日後、 「遅れてすみません。今週中に出します」といった内容の返事が届きました。 ところが、次の週になっても、その次の週になってもなにも音沙汰がありません。

幸い、僕の周りは、同人関係に詳しい人に事欠きませんので、 友人Y1、Y2に聞いてみました。YはYu-jinのYですよ。念のため。

Y1「同人だと3ヶ月は基本だよ」
Y2「2ヶ月は普通にかかりますね」

えぇ〜?そうなの〜?。でもよー、今週中に出すって言ってたんだよー

Y2「それはおかしいですね」

ということで、同人に詳しい人にとっても異常な事態な感じです。 で、結局どうしたのかというと、別の友人と相談の上、 放置しておくことにしました(笑)。 要するに、このままだまっていたらいつ送られてくるかなーと言うわけです。

ちなみに、詳しい日付は、

9/?? 僕:申し込み
9/?? Aさん:申し込み確認
9/14 僕:振込み
9/15 僕:メールで振込みを連絡
10/xx 僕:問い合わせ
10/xx Aさん:「今週中に送ります」

1/4現在ですが、今もって送られてきていません。 ここまでくると、 どのくらいまでひっぱるかな〜と逆に楽しみでもあります(笑)。

同人にも在庫管理を

通販といっても、 生産→在庫→発送という流れはありますから、 店の在庫管理問題と同じように考えることができます。 要するに、在庫は少ないほうがいいが、品切れは困る、 そして生産はすぐにできるわけではない、というアレです。 このような場合を扱う方法があるわけですが、 そのためには、需給の量を見定める必要があります。 これを失敗すると、在庫がいっぱいになったり、 品切れになったりするわけです。

さて、同人の通販といえば、仄香スクリーンセイバーもそうです。 現在は販売を休止している1、はず、なのですが、 ときおりちらほらと振込まれる人がいらっしゃいます。 このような場合、需要を予測することは不可能です。 これに対処する方法には

の2つが考えられます。

それだけの話であれば簡単なのですが、 実は、注文→生産→発送の段階は、 それぞれ独立したステップとして順番に進行するわけではなく、 互いに依存したより小さな段階(サブステップと呼ぶ)として順番に進行するわけです。 例えば、仄香スクリーンセイバーはフロッピー配布ですから、生産の段階は

a.ハードディスクからフロッピーにコピー
b.フロッピーからインストールのテスト
c.宛名書き
d.封筒を閉じる

というサブステップから構成されます。 これらの作業は、a、bを行いながらcを行って、すべてが終わってからdを行います。 もし、在庫があれば、aの作業を行う必要はありません。 aとbを行う時間とcを行う時間を比較すると、 aとbを行う時間のほうが長くなります。 したがって、在庫を用意することは発送までの応答時間の短縮に貢献することがいえます。

しかし、在庫を取り出す時間が0でない場合を考えましょう。 要するに、

a'.在庫を倉庫からもってくる

というサブステップが存在する場合です。

このとき、それぞれのサブステップに要する時間、T(a)<T(a')なら在庫をもつ必要がなくなります。 作ったほうが早いからですね。 要因は、在庫が別の部屋にあるとか、 倉庫は他の人が管理しているとか、 今職場にいるとか、いろいろ考えられます。

ということで、仄香スクリーンセイバーはほんとは在庫を持たないほうがいいのですが、 現実問題としては在庫がたくさんあります。 なぜでしょうか? それは、在庫は在庫でも、売れ残りの不良在庫なのです。 注文もほとんどないので、ソースをフリーにしようかと思ってますが、 そうなると、この不良在庫はゴミになることが確定してしまうので、 踏みきれなくて困ってます(笑)。

出前と自前によるマスク生成

この考え方は最適化でも同じです。 在庫を用意するのは一見、高速な気がしますが、 実際には製品を作ったほうが速いことも十分にありうるわけです。

なんの話しかというと、 WonderWitchにおけるマスク生成の話です。 WonderWitchにおいて、色抜き転送をする場合、マスクを先に作っておいたほうがいいか、 それとも動的に生成したほうがいいか、ということです。

WonderWitchにおけるマスクの生成をするためには、 WonderWitchのVRAMの表現形式を説明する必要があります。 図1のようになっています。

画像に対するメモリ表現
図1:画像に対するメモリ表現

最下段が実際に表示されるピクセルの並びです。 WonderWitchでは1ピクセルは2bitで表しているので(WonderSwan Colorでは違うモードもあります)、 ピクセルのデータは概念上、Pixel Repsのようになるわけです。 メモリ上での表現はMemory Repsのようになっています。 最初の1Byteには連続する8ピクセルの上位ビットだけが格納されているということですね。

この形式に対してマスク(ここでは0を透過とするようなマスクとしましょう)を生成するのは、 非常に簡単です。axにデータが入っているとすれば、
or  al, ah
mov ah, al

これでOKです。原理を説明する必要もないほど簡単です。 ほんとはこれだけで話をすませるつもりでしたが、もう少し話は続きます。

さて、マスクをメモリにあらかじめ在庫してある場合、axにマスクを用意するためには
mov ax, [bx]

となります。 一方、動的に生成する場合は

mov ax, [bx]
or  al, ah
mov ah, al
のようになりますから、 2クロック多くなるわけです。 ということで、動的マスク生成は、マスク在庫よりも2クロック低速である。 と結論したいところですが、そう簡単ではなさそうです。

コードの解析

マスク在庫の場合、 メモリからデータを読み出す回数が一回増えることになりますから、 もし、メモリからのデータ転送がなんらかの理由で低速であると、 2クロックの差がなくなることになります。 なにか、理由があったり、ということはないでしょうか? とりあえず、実際のコードを考えてみることにします。

まずは動的にマスクを生成する場合です。
bx:スプライトデータ  di:転送先イメージ

として、コードは、

1: mov ax, [bx]
2: mov cx, ax
3: or  al, ah
4: mov ah, al
5: mov dx, [di]
6: xor cx, dx
7: and ax, cx
8: xor dx, ax
9: mov [di], dx

となります。 一方、 マスクデータがあるとき、

si:マスクデータ

とすれば、コードは

1: mov ax, [bx]
2: mov dx, [di]
3: mov cx, [si]
4: xor ax, dx
5: and ax, cx
6: xor dx, ax
7: mov [di], dx

となります。

今まで、それぞれの命令は、すべて1クロックで処理されると思っていましたが、 Caribbean Seaさんの解説によると、 メモリアクセスをする場合には、命令フェッチがストールするようです。 ということは、上の二つのコードはすべて1クロックの命令ですから、 影響を受けます。

それぞれのコードの実行サイクルがどのようになるかを次に示します(間違ってる可能性もありありです)。 各ユニットを
F:fetch D:decode E:execute
とします。 マスクデータを生成する場合には、
F 1 2 - 3 4 5 6 - 7 8 9
D - 1 2 - 3 4 5 6 - 7 8 9
E - - 1 2 - 3 4 5 6 - 7 8 9
となりますから、最初の命令が実行ユニットで実行されてから、 最後の命令が実行されるまでに13クロックかかります。

マスクデータを読み込む場合には、
F 1 2 - - 3 4 - 5 6 7
D - 1 2 - - 3 4 - 5 6 7
E - - 1 2 - - 3 4 - 5 6 7
となり、10クロックかかります。

最適化のツボ

メモリアクセス時に命令フェッチがストールすることを考えると、 命令フェッチが少なくて、実行クロックが多いような命令がお得です。 そんな命令はというと…。あります。

add reg, mem
系の命令です。 この命令、regにmemの内容を加えるわけですから、
mov temp, mem
add reg, temp
というわけで、2クロックかかるにもかかわらず、命令長は2byteです。

それでは、この命令を使って高速化できないか、検討してみましょう。

・・・。どうにもならず。(笑)

どうも有効に利用することができませんでした。 理由は簡単、データの依存関係が厳しく、命令の入れ替えが全くできないことと、 データの再利用が必ず行われているので、データをレジスタに放り込んでおく必要があるためです。 これらを無理に回避しようとすると命令数が増えるので、 結局変わりません(笑)。

試しのコードを示します。 まずはデータからマスクを生成する方法です。

1: mov ax, [bx]
2: mov dx, ax
3: or  ah, al
4: mov al, ah
5: and dx, ax
6: not ax
7: and ax, [di]
8: or  ax, dx
9: mov [di], ax

こうなりました。実行サイクルの様子は

F 1 2 - 3 4 5 6 7 8 - 9
D - 1 2 - 3 4 5 6 7 8 - 9
E - - 1 2 - 3 4 5 6 7 7 8 9

となり、やはり13クロックかかります。

これに対し、マスクをあらかじめ用意しておく方法は、

1: mov ax, [di]
2: mov dx, ax
3: and ax, [bx]
4: not dx
5: and dx, [di]
6: or  ax, dx
7: mov [di], ax

とコーディングできました。このコードは

F 1 2 - 3 4 - 5 6 - 7
D - 1 2 - 3 4 - 5 6 - 7
E - - 1 2 - 3 3 4 5 5 6 7

と実行され、やはり10クロックかかります。 ということで、意味がなかったんですな。

過去の栄光による高速化

普通の人は、ここまでの話に疑問を持たないでしょう。 しかし、大きな落とし穴があって、無駄な命令が一つ入っているのです。 その解説はすでに第9回でしているわけで、 ちゃんとコーダ部屋を読んでいれば気がつけたはずです。 ちなみに、僕は普通の人を通り越して間抜けですね(笑)。

さて、どの命令が無駄かというと、マスクとスプライトデータをandしているところです。 スプライトデータには、透過部分にゴミが入っているわけでないので、 わざわざマスクする必要はありません。気づけよな〜>僕

この命令を取り除くと、前節の1命令で2つの動作を行う命令が有効に使えます。 どうなるか書きなおしてみましょう。 マスクデータを生成する場合は、
1: mov ax, [bx]
2: mov dx, ax
3: or  ah, al
4: mov al, ah
5: or  ax, [di]
6: sub ax, dx
7: mov [di], ax
となり、2命令減です。そして、実行サイクルを見ると

F 1 2 - 3 4 5 6 - 7
D - 1 2 - 3 4 5 6 - 7
E - - 1 2 - 3 4 5 5 6 7
ですから、9クロックで実行できそうです。 マスクをあらかじめ用意した場合よりも速くなりました。

ちょっと待ってください。 マスクをあらかじめ用意した場合も速くなったりしませんか?
1: mov ax, [si]
2: and ax, [di]
3: or  ax, [bx]
4: mov [di], ax

F 1 2 - - 3 4
D - 1 2 - - 3 4 -
E - - 1 2 2 - 3 3 4

・・・ありゃ。より短くなってしまいました(笑)。 実行は7クロックですね。

しつこく考察

ここまでの議論では触れていませんが、 実際にコードを使用するときに問題になることがあります。 アドレッシングレジスタの更新です。

色抜き転送が使われるのは、スプライト的な使用がメインなわけです。 ということは、8x8ピクセルのパターンを転送する、といったような利用です。 この場合には、読込・書込するアドレスはループごとにインクリメント等をしなければなりません。 したがって、読込・書込のアドレスを表すレジスタ数だけ命令数が増えることになります。 動的にマスクを生成する場合にはレジスタ数が2つであるのに対し、 マスクをあらかじめ用意しておく場合ではレジスタ数が3つです。 この結果、両者の差は1クロックとなりました。

指摘される前に予防線をはっておきましょう。 ループ用のレジスタを使って

1: mov ax, [si +cx]
2: and ax, [di +cx]
3: or  ax, [bx +cx]
4: mov [di +cx], ax

とすればアドレスの移動は必要無くなるように思えます。 思いました。残念でした。このようにアドレスを指定すると、 アドレス計算に1クロックかかりますので、速くなりません。

最高速−アルゴリズム=データ構造

データ構造を工夫すると、 マスクをあらかじめ用意しておく方法におけるアドレス用のレジスタ数を減らすことができます。 アイデアとしては、 スプライトパターンデータとスプライトマスクデータの相対的な位置を決めておき、 ハードコーディングしてしまう、というだけのことです。 例えば、8x8のスプライト専用ということにして、 スプライトパターン(2x8byte)の後ろにマスクデータを配置しておきます。 これなら、コードは
mov ax, [bx +16]             マスクデータの読出
and ax, [di]
or  ax, [bx]
mov [di], ax
となり、必要なレジスタを一つ少なくすることができます。 もし、転送サイズを可変にしたい場合には、 8ピクセルごとにスプライトパターンとマスクデータを交互に置くとよいでしょう。

さらにやる気があるなら、 自己コード書き換えするのもよい方法です。 これなら、読込と書込のレジスタを共用することもできなくありません。 ただし、セグメントに注意する必要がありますね。

うわごと

思いついて、文章を用意し始めてから二ヶ月もたってしまいました。 その間に、Wonder Swan Colorが出てしまってネタが使えないかと思いましたが、 カラーでもモードによっては有効なので、ほっと一安心。

それはともかく、 こっそりとアクセス解析をくっつけてたりしますが、 意外なキーワードの検索で飛んでくる方がいたりするようです。 全く見当違いというわけでもないのですが、 おそらく必要な情報は得られなかったんじゃないかなぁ〜とか思います。 でも、検索キーワードは今後の参考にさせてもらうので勘弁してください。

できれば、過去の分に関しても参考文献リンクを充実させたいですが、 時間的に無理っぽくて申し訳ありませんー。 そんな感じで、いつ更新するかわからないペースで更新するつもりなので、 今年もよろしくお願いします。

そうそう、例のCG集ですが、100%忘れられているに違いないのでもう一回問い合わせることにします(笑)。 でわ。

参考文献



1.販売を休止している
インストーラで表示しているTUATMCCをD5.に変更することができないという理由なのですが。

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


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


sanami@aya.or.jp