Hatena::ブログ(Diary)

やねうらお−ノーゲーム・ノーライフ このページをアンテナに追加 RSSフィード

GT-Rの買取ならここですわ。どこよりも高く買取ってもらえるはず。お勧め!GT-R 買取
電王戦出場記念! 書籍化されたで! 監修したで!(`ω´) 絶版なってしもた Kindle版で復活!! 記事書いたで!
解析魔法少女美咲ちゃん マジカル・オープン!

YaneuLabs / やねうら王公式 / やねうらおにメール / twitter / プロフィール

 | 

2004-02-25 count 0 bits

[][] を含むブックマーク のブックマークコメント

「ビット演算の超魔術」を書くに際して、いくつかの本を読んでみている。

(書くことが決まったわけではない。勝手に調べてるだけ)

まずは「Hacker's Delight」。

Lucilleの作者もお勧めしてたんで買ってみた。

名前とは裏腹にビット演算系の書籍だ。

ぱっと見、半分以上知ってるテクなんだけどな..

しかし、「Effective Java Programming」で有名なJosh Bloch氏も

本の裏に「この本、すごーだ!おまえの本棚のKnuth本の横にならべとけ!」

コメントを寄せている。まあ、それくらいの価値はある。


その中で32bit整数の0になっているbitの数を数えるというセクションがある。その話題自体はよくあるものだが、ひとつだけ知らないテクが載っていた。そしてそれは驚愕に値するものだった。

int nlz(unsigned k){
  union {
    unsigned asInt[2];
    double asDouble;
  };
  int n;
  asDouble = (double)k + 0.5;
  n = 1054 - (asInt[LE] >> 20); // little endianなら1,big endianなら0
  return n;
}

( Д)゜゜ using IEEE floating point!!!

トラックバック - http://d.hatena.ne.jp/yaneurao/20040225

2004-02-21 やばい。ほんとやばい。

[][][]多変量解析,モンテカルロ法 多変量解析,モンテカルロ法を含むブックマーク 多変量解析,モンテカルロ法のブックマークコメント

やばいですよ、やばい。すごいやばいですよ。

3Dやるのに行列と4元数ぐらい知ってればポリゴンぐらい動かせるだろとか

思ってる人もいるだろうけど、そんな甘くもないんですよ。

まず最初に、ポリゴンの頂点を球とかボックスとかでフィッティングする

作業が必要になるんです。axis-alignedなボックス(AABB)でいいやーとか、

そんなこと言うなまいきな子はお尻ぺんぺんですよと。*1


それで、フィッティングを少し真面目にやろうと思ったらとりあえずは

共分散行列と最小二乗法とか必要になって。最小二乗法って二乗したやつ

最小化する係数を決定しないといけない。


すこし凝った図形でフィッティングしようと思うと、二乗したやつ最小化

するだけでひと苦労。最小値求めるのにベクトルでの微分とか出てきて

「あーベクトル解析とか多変量解析とかもう少し真面目に勉強しとけば

よかったなー」とか考えたりして全然はかどらねぇ。仕方ないんで、

多変量解析の本2冊買ってきて、勉強しようかと少し開いてわからない

キーワードをwebで調べたりしてるうちに、えらいもん見つけて

しまいましたよ!!ここまでが前振りですよ!前振り! ← 前振り長いねんヽ(`Д´)ノ


http://www.sci.kagoshima-u.ac.jp/~ebsa/index.html

これですよ、これ。多変量解析とかモンテカルロ積分の教科書とか

まるごとWebにあがってるんですよ。悔しいことに私がいま買ってきた本より

詳しい本が! くそー。金かえせー。くそー。この馬鹿野郎ー!(俺がな)

*1:フィッティング作業を実行時にやるわけではないので、多少複雑な図形にフィッティングしても、実行時の判定が容易な図形であればAABBなんかよか断然精度がいいのです。

dappydappy 2005/07/24 21:55 >WEB本
ありがとう。

yaneuraoyaneurao 2005/07/24 22:07 いえいえ(´ー`)

dappydappy 2005/07/24 22:16 はやっ。本月(2004年2月)は特にピンポイントで楽しめした。

gpuppurgpuppur 2009/02/27 02:56 毎フレーム変形するポリゴンを扱うときには計算速くてメモリ使用量が少ないAABBを使ったりします。
OBBは共分散行列とか計算しないといけないので重くてメモリ使用量も多いわりにはそれほど小さくなってないと思うので前計算でOBBを作る場合ぐらいにしか使えないと思います。
AABBより小さくしたければDOPの方がOBBより計算が少なくメモリ使用量も少なめでいいと思います。

yaneuraoyaneurao 2009/02/27 03:18 何故に5年前の記事のレスがいまごろ…

トラックバック - http://d.hatena.ne.jp/yaneurao/20040221

2004-02-20 本は買わなくてもいいのか

[][]C#入門書 C#入門書を含むブックマーク C#入門書のブックマークコメント

ちょっとあぶくゼニが手に入ったのでこのお金は全部本でも買ってやるかとかねてから買おうと思っていたC#の本をチェックしてたら

http://www.atmarkit.co.jp/fdotnet/csharp_abc2/index/

そのままWebで見れました。ヽ(´ー`)ノ

しかも大幅に書き足してあるし..。本の立場は一体..。

だいたい、いまどき、本買わないと読めない情報ってなんだろう。

たいていの情報は根気よく探せばWebで拾える気がする。

ただ、Webだとまとまっていないので、系統だてて理解するのに時間がかかる。その時間とのトレードオフなわけだ。

..と自分で書いてて、なんだか頭の悪い学生のような発言だなぁとか思った。丸々Webにあがってるんだからトレードオフでも何でもない気がする。まずはWeb上で探して、どうしても入手できないような情報なら本屋で手にとって見て、欲しけりゃ買えってことだね。うん。

[][]近未来ゲームプログラミングの現場 近未来のゲームプログラミングの現場を含むブックマーク 近未来のゲームプログラミングの現場のブックマークコメント

10年後のゲーム製作の現場ではきっと数学が出来るやつが

一番偉かったりするんだろな。

東大出身の若手プログラマとかに「ルジャンドル陪関数も知らないのかよ。

お前、超クズだな」とかくそみそに言われ、「クォータニオンなんざ、

いまどき小学生でも知ってんだよ!馬鹿かお前!」とどやされ、

「テンソル球面調和関数も知らないで、よくプログラマやってるな!

恥ずかしくないのか、この糞豚が!」

...

そんなん言われたら泣きそうだよ、ママン。・゜・(ノД`)・゜・。

トラックバック - http://d.hatena.ne.jp/yaneurao/20040220

2004-02-16 3D勉強がんばってます(`・ω・´)シャキーン

[][] FF12  FF12を含むブックマーク  FF12のブックマークコメント

FF12キャラとかはもうかなり細かく描き込んであって、二次元キャラとくらべても全然遜色とかないのだが、動きにはまだ不自然さが目立つ。重量感がてんでない。

原因をいろいろ考えてみたが、どのみち粘土細工に関節を仕込んで動かすのはどうしてもこのへんが限界なのかも知れない。もうそろそろ筋肉や動きをもう少しまじめに物理シミュレーションしなければならない時期に来ているのだろうと思った。

[][][] 軸回転行列  軸回転行列を含むブックマーク  軸回転行列のブックマークコメント

ゲームプログラミングの3Dグラフィック数学」をちょっと真面目に読んでみたりしてるんだけど、これ本当、教科書としてはすごくいい本だと思う。このあと何十年たってもきっと色あせないと思う。

ところで、この本のなかでP.62に軸回転をskew(外積の書き換えに使う行列。同書、式1.25の行列)を用いて書いてあるんだけどskewを使うならskewだけで A(A・P)=(skew(A)^ 2 +1)P を用いて、

軸回転行列M = I + s sinθ + s^2(1-cosθ) , s = skew(A)

と一回は導出して見せるべきだと思うんだけどなぁ。式1.20を持ち出したのがまずく、結局、同書ではこの部分、軸回転行列をshewだけで表せずじまいになっている。


3D関連の記事、書き始めたので興味のある人はどうぞ。

http://yaneu.com/yaneurao/3dcg/

kcrtkcrt 2004/02/17 02:04 2DのRPGゲームって、このままなくなってしまうんでしょうか?ゼルダもGC版よりスーファミの頃のヤツが好きだったりするんですけど。

yaneuraoyaneurao 2004/02/17 02:16 携帯マシンならともかく、家庭用で2Dをやって、見るに耐えるクオリティにしようと思うと凄い数のドットが必要になるので..なかなか難しいんじゃないでしょうか..

k_ahiruk_ahiru 2004/02/17 13:59 なんかどっかで見たことがあるようなデザインですね>3dcg。紅茶が飲みたい。

yaneuraoyaneurao 2004/02/17 19:16 t-potリスペクトっつーことで、デザインを似せてみますた。○オマージュ ×パクリ

トラックバック - http://d.hatena.ne.jp/yaneurao/20040216

2004-02-12 CORE WARS

[][][]プログラムとプログラムを戦わせる プログラムとプログラムを戦わせるを含むブックマーク プログラムとプログラムを戦わせるのブックマークコメント

その昔、CORE WARS*1という、プログラムとプログラムを戦わせるソフトがあったが、あれの現代版を考えた。

以下、その案。

・8086のコードをエミュレートして戦う。(ただし全ての命令が使用できるわけではない)

・プログラムは通常のアセンブラなり、OllyDbgのラインアセンブラなりで勝手にやれと。

・プログラムの実行は、メモリ空間をデフラグのようにビジュアライズされるのでそれを見て楽しむ。(出来れば3D的な表現等を取り入れてあればbetter)

ルール

・相手のプロセスの実行しているアドレス(EIP)にwriteすれば勝ち。

・実行は、64k(16bit)のアドレス空間で行なわれる。

・実行イメージが配置されるメモリアドレスはランダム。

・5回の勝負で決着をつける。

APIは INT xxをAPI呼び出し用に使って、debug用表示や、プロセスのfork等、ゲームバランスを調整するためのものを用意するかも。

CORE WARSに触れたのはいまから17年ほど前。私は当時、中学生だったと思う。

メモリfillや、8byteごとにwriteしていく(一寸法師と呼ばれる)ような単純なプログラムが勝利するゲームバランスにすると面白くない。そのへんをどう調整するかが課題だろう。

当時「ダロス」というアニメを見て、そのなかで自己修復機能を持ったダロスという人工建造物が出てくるのだが、これに影響を受けてCORE WARS用にそういうプログラムを書いた覚えがある。(30バイト程度のプログラムだが)

自分のコピーを作り、繁殖する。自分の作ったコピーの生存フラグをチェックし、破損していれば壊されたと見なして、再度自分のコピーを作るのだ。いま考えれば、これは一種のwormなのだが。こういう仮想マシン上で17年も前にwormを書いていたとは..ひょっとすると私が世界初ではないかしらん。(知らんけど) しかも中学生のときとは..かなりキチガイじみた少年だったんだなぁ..などと感心したりする。

まあ、そんなことはどうでもいいので、誰か作ってもらえんかの。>このゲーム


ABAさんがネタにしてくれたんで紹介:

http://d.hatena.ne.jp/ABA/20040212#p1

> ポケモンみたいになにか集めさせようか。インストラクションセットとか、パイプラインとか。

>「うなれオレの128段スーパーハイパーパイプライン!」「なんの我が1024bitVVVLIWに敵なし!」

それ、めっちゃ面白いんですけど(ネタとしては)

*1:いまでも遊べるようだ。→http://www.koth.org/pmars/

mihael2mihael2 2004/02/12 22:57 やねさんが作るんじゃないんかいっ!!!(わかりやすいツッコミからコメントスタート)

mihael2mihael2 2004/02/13 07:06 COREWARSが想像出来ないんすけども、1クロック毎に互いのプログラムがマルチタスクに動いているんでしょうか。

mihael2mihael2 2004/02/13 07:07 ルールとして、重量戦(プログラムサイズ単位で戦う)を導入するのはどうでしょう

yaneuraoyaneurao 2004/02/13 07:19 COREWARSは1クロックずつ交互実行で、forkに相当する命令を実行した場合、平行スレッド(並列ではない)扱いだった気がします。だもんで無理にforkしても何も有利にはならない、という。プログラムサイズ単位で戦うのは..このゲーム、プログラムサイズでかくてもあまり有利になりにくいので

yaneuraoyaneurao 2004/02/13 07:23 あまり意味が無いと思うのです。プログラムが大きいと破壊されやすくなるので。んで、無効な命令(null/nop)を実行したら負けなので。まあ、x86のエミュレーションならわかりやすくnopを無効命令扱いして、0x90を書き込むアタックをしていくことになるんでしょうけど。

mihael2mihael2 2004/02/13 10:18 むむむ、じゃあフラッグ(特定アドレスを全部塗りつぶしたら勝ち)とか宝探し(あるアドレスに配置された宝を取る(値を取得する)と次のアドレスが指示される)とか……ウィルス対戦じゃなくなってますが

mihael2mihael2 2004/02/13 10:19 やねさんが中学生の齢に書かれたwarmみたいなアプリが勝つゲームが面白そうですな

nyaa1nyaa1 2004/06/07 13:40 はじめまして。mihael2さんのところから飛んできました。

nyaa1nyaa1 2004/06/07 13:42 自分のコピーを作り、繁殖する。自分の作ったコピーの生存フラグをチェックし、破損していれば壊されたと見なして、再度自分のコピーを作るのだ。<ロードモナーク(ファルコム)を連想してしまいました。

2004-02-07 自動crack soft!?

[] を含むブックマーク のブックマークコメント

いま解析本書いてるのだが、PEヘッダの構造調べている過程でちょっとやばいものが出来てしまった。

文字列をサーチして、そこを参照しているコードを特定して、そこからバックトレースして、そこに分岐しているコードを潰すプログラムだ。

これ使うと何の知識もなくても「パスワードが間違ってます」とかそういうシリアル入力のときの失敗文字列を入れると、ここに分岐してくるのを潰すのでシリアル入力が完了してしまう。これ下手すると、現存するシェアウェアの半分ぐらいが自動的にcrackできてしまうんじゃないかと。(試してないけど)

ついでにマウスのみで操作が完了するように改造しようかとか少し思ったが、そもそもこれ合法なのかという危惧もある。これの応用で実行モジュールのプロセスメモリのsnapshotをとって、指定した文字列を表示している部分を呼び出さないようにも出来るわけでインストール時のシリアルチェックとかもスキップ出来てしまう。

ちょっとさすがにやりすぎのような気がするので、これらは闇に葬ることにする予定だが、もし欲しい人が居るなら、この記事にコメントして欲しい。要望が多ければ公開しなくもないし、需要があるようなら、完成度を高めてシェアウェアにしなくもない。

あっ。でも悪用厳禁な。自分で作ったプログラムのパッチ当てるの専用ってことで。

kcrtkcrt 2004/02/08 10:55 悪用厳禁ですかw。応用効きそう、例えば一昔前のCDチェッ(以下自粛

nevilnevil 2004/02/10 09:12 おもろすぎます。( ゜д゜)ホスィ…

aleaalea 2004/02/10 09:45 オモロー(゜Д゜)…日記タイトルがどんどん伸びてる…

yaneuraoyaneurao 2004/02/10 09:54 ひょっとしたら、商品化するかも..。

yaneuraoyaneurao 2004/02/10 19:27 やっぱししばらく頭を冷やします..(´ω`)

mihael2mihael2 2004/02/10 21:52 個人的にはちょっとやそっとじゃクラックできないコードの書き方の方が知りたいっす。需要はなさそうだけれども

k_ahiruk_ahiru 2004/02/10 23:47 需要はありそうな。

nevilnevil 2004/02/11 12:04 どっちも需要はあるんじゃないかな。良いか悪いかはヌキにして

ohmyahiyonohmyahiyon 2004/02/11 19:14 これやりだすと止まりませんよ。ICE・プロセスメモリエディタ系に進むことになります。静的サーチでは逆汗して眺めるのと変わりません。

ohmyahiyonohmyahiyon 2004/02/11 19:19 2〜3の逆参照では「文字列を表示するルーチンを呼び出さない」だけになりかねないので、どこまでが意味のあるチェックルーチンなのかを見極めてバックトレースするかの点でムズイですのぉ。

ohmyahiyonohmyahiyon 2004/02/11 19:24 レジスタ間接コールを考慮して実用的なものにしようとすると、ゲーム作ってる暇はなくなりますぜダンナ。

yaneuraoyaneurao 2004/02/12 04:27 いやー、そこまで複雑のは解析できなくていいのです。逆アセして眺めるのと変わらなくても一般人はそれ出来ないので、誰でも出来るようになるというのが大きいわけで。

mihael2mihael2 2004/02/12 06:52 解析の過程がビジュアルにわかると面白いと思うのですが、逆アセするとなると、大抵の使用許諾(逆アセ禁止)に違反しますね……

churoschuros 2004/02/12 11:12 要望あります! 自分で作ったプログラムのパッチ当てるの専用」』です。よろしくおねがいします。

yaneuraoyaneurao 2004/02/12 15:57 とりあえずやばそうなので、しばらく寝かせておくことにする..

 | 

1900 | 01 |
2004 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2012 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2013 | 01 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2014 | 01 | 02 | 03 | 04 | 06 | 08 | 10 | 11 | 12 |
2015 | 01 | 02 |


Microsoft MVP
Microsoft MVP Visual C# 2006.07-2011.06