No Such Blog or Diary

いろいろなところで使われている LZSS の実装は多種多様である．なので，ありそうなパターンに対応できるようにソースを書いてみた．速度は度外視．あとで最適化すればいいし．圧縮部分の検索ルーチンをもう少し大きなハッシュにしたほうが速いだろうか？　ま，どうでもいいか．つーことで，そーすをおいておく．

コンテストの規定は画像処理プログラムを書いて， fingerprint を実行するたびに異なるように入れろと．さたに，その fingerprint に意味はなくてもいいけどあるほうがよいと．んで，受賞した単に減色するだけのプログラムを見たけど...　まったく普通のプログラムにしか見えん．種明かしとしてはスタックフレームにローカル変数の値が残ることを利用して連続しているらしい．うーん，こんな方法思いつかんなぁ．もっと柔軟にならねば．

Singleton パターンではインスタンスを一つ作ってそれを使いまわす．そのために，そのインスタンスを取得する関数でインスタンスを作ってあるかを調べ，あったらそれをかえす，なければ新しく作るという動作をさせるのが一番楽．で，コンストラクタはプライベートにしておくと．

しかしながらとあるプログラマは次のようなコードを書いて，うまく動かないと騒いでいた．

AClass* AClass::getInstance(){
	static bool isFirst = false;
	if(!isFirst){
		instance = new AClass();
	}
	return instance;
}

isFirst が false のままだし...　あなたインスタンス取得するたびに新しいの作るんですか？　Singleton とか言ってたのにインスタンスはひとつじゃないんですね．そもそも isFirst などというフラグを持たずに if(!instance) と書いていれば間違いがなかったものを．

とりあえず今後の参考のためにこの事実を記しておこう．ちなみに彼はコンストラクタすらもプライベートでなかったという...　（まあ，このソース以外では正しいコードを書いていたそうだが．）

二つの和を求めるプログラムがある．

#include<iostream>
using namespace std;
int main(int argc, char *argv[]){
	double d = 1e300;
	double sum = 0;
	for(int i = 0; i < 10000000; i++){ sum+=d; }
	cout << sum << endl;
}

#include<iostream>
using namespace std;
int main(int argc, char *argv[]){
	double d = 1e308;
	double sum = 0;
	for(int i = 0; i < 10000000; i++){ sum+=d; }
	cout << sum << endl;
}

上は 1e300 を 100000000 回足した和を求める．下は 1e308 を 100000000 回足した和を求める．これらのプログラムを実行した場合，普通は速度の違いなどないように思えるが...　実際に動かすと上が 0.148s で下が 0m3.692s と劇的に違う．これは double が 1.7e308 程度までしか値を保持できず，これ以上ではオーバーフローして Inf になってしまうことによる．で，Inf に値を足し続けるので遅くなると．何で Inf で遅くなるのかしらんけど．

なんとなく思いついたのでやってみた．C 言語で書いたプログラムの（ブートストラップ後の）エントリポイントは main 関数なわけだけど，アセンブラレベルでは結局のところ call main して main というラベルにとんでいるだけ．ということは，main は別にC言語の関数ではなく変数でもよい（main というラベルが作られる）．これを実証するコードは以下のとおり．

こいつは HelloWorld を表示するが，main は関数でなく変数である．

#include <stdio.h>
 
int f()
{
	printf("HelloWorld!\n");
	return 0;
}
 
int main[] = {0xB8909090, (int)f, 0x9090E0FF};
 
/*
int main  = 0xB8909090;
int main2 = (int)f;
int main3 = 0x9090E0FF;
 */
/*
struct main {
	int m1;	int m2;	int m3;
} main = {0xB8909090, (int)f, 0x9090E0FF};
 */

main の定義をコメントアウトしている形（構造体，複数個の連続した変数）にしても動く．原理としては main というラベルに飛ばされてくるので，そこに関数本体である f へのジャンプを行うマシン語を埋め込んで f へジャンプさせる．ジャンプのコードはi386で

90             NOP
90             NOP
90             NOP
B8 XXXXXXXX    MOVE EAX, f
FF E0          JMP EAX
90             NOP
90             NOP

とかけるので，これらのマシン後が実行されるように main 変数に値を入れている．

ついでに C++ 版も．

#include <cstdio>
struct main {
	int ins[5];
	static int f() {
		puts("HelloWorld!");
		return 0;
	}
} main = {0xB8909090, (int)(main::f), 0xE0FF};

色々がんばってるなぁと思ってみたり．tokenizer, regex, format あたりは結構よさげ．スクリプトでは複雑すぎて書きにくいけど文字列の扱いが...　な問題でありがたい．あと乱数にメルセンヌツイスター使えるのもセンスいいねぇ．ディレクトリ関係をまとめた部分ではパスの演算子に / が使えるのも面白い．さて，次は関数型言語Ｃ＋＋の部分に踏み込むとするか．