◆2ちゃんねるトリップ計算機 うとりっぱー◆
1.このプログラムについて
1.1 これは何をするものか
2ちゃんねる掲示板で導入されているトリップ(ひとり用キャップ)を
計算するものです。
このソフトと同じ目的で開発されたものに、「見知らぬ国のトリッパー(w」
などがあります(参考URL: http://isweb34.infoseek.co.jp/computer/tripsage/)。
1.2 このプログラムの特徴
- UFC-crypt を利用した高速検索
- さらに、MMX を利用した高速 crypt ルーチン
- 正規表現を利用可能
などなど
1.3 気になる速度は…
私のマシン (PIII 1000MHz, 133MHz x 8) で正規表現でない文字列の検索だと
175kKey/s 程度出ます。正規表現だと複雑さに応じて遅くなります。
#それでも全空間検索するには10年のオーダの時間がかかります:-)
しかし、Athlon/Duron/Coppermine Celeron等のCPUではクロックに
比例した性能がでないことがあります。
これは、MMX のルーチンによるものではなく、C 版の UFC-crypt を
そのまま使っても同様の速度かそれ以下しか出ません。
2次キャッシュアクセスのレイテンシやキャッシュミスヒット時の
ラインの充填時間が響いてくるアルゴリズムになっているので、
CPU の特性に応じて速くなったり遅くなったりするようです。
1.4 トリップについて
２ちゃんねるのトリップは、crypt(3) と呼ばれる関数を使って、
計算された結果(13文字)の下8文字を使っています。出力される
各文字は計算結果を 6bit 毎に区切って文字にしているので、
出現する文字は 64種類ということになります(a-zA-Z0-9./)。
それ以外の文字は出て来ません。crypt の計算結果は 64bit の
長さになりますが、6bit ずつ区切ると最後の 4bit が余ります。
このため、トリップの右端には 16種類(.26AEIMQUYcgkosw)の文字
しか出現しません。
また、暗号化の際に暗号化のパターンを乱すために salt と
呼ばれる 12bit(0〜4096) の数字が用いられます。
※2002/10/3から下10桁になりました。
2.利用方法
2.1 ビルドの方法
配布はソースコードのみになっています。
autoconf などの親切な設定にはなっていないので、ご自分の環境に
合わせて Makefile (またはソース) を修正し、make して実行ファイルを
生成してください。運がよければ Makefile は修正しなくても
make 一発でコマンドが完成します。
ご使用のマシンが MMX がない、あるいは x86 以外であれば、
Makefile の DEFINES から -DHAVE_MMX を消してください。
Coppermine Celeron (L2キャッシュが 128k のモデル) のように
キャッシュの少ないマシンでは、-DSMALL_CACHE を付けてコンパイル
すると、劇的に性能が上がる場合があります。
なお、MMX 使用のルーチンはその CPU で MMX がサポートされているか
どうかチェックしていませんのでご注意ください(^^;
MMX 命令を含んだバイナリを MMX なしのマシンで動作させた場合、
不正命令エラーか何かがでると思われます。
2.2 起動方法
出来上がった実行ファイル utripper をパスの通っているところに置いて
実行してください。検索する文字列を引数に指定するとその文字列を探して
画面とログファイルに出力します。
使用可能なオプション:
-i 大文字小文字を区別しない (デフォルトは区別する)
-s 数字 乱数の系列を指定する
-r 基本正規表現を使ったマッチを行う (※ -i と併用可)
-e 拡張正規表現を使ったマッチを行う (※ -i と併用可)
-l ファイル名 ログファイルの名前を指定する (デフォルトはカレント
ディレクトリの utripper.log) ※ログファイルは常に
追加モードで書き込まれます。
-n デフォルトではキーを連番で検索していきますが、
-n オプションを指定するとキーをランダムに生成して
検索します。salt は 1000000 キーを検索するごとに
ランダムに変更されます。
希望のキーが出るまでの平均時間は連番検索と変わらないと
思いますが、宝くじをいつもバラで買っている人の気分で
御利用ください:-)
-p 数字 プロセスの優先度を指定します。通常、0 が最高で 20 が最低です。
数字については、OS 付属の nice(2) のマニュアルを参照してください。
Win32 版では、数字は 0, 1, 2 で、0 が優先度高, 1 が通常、
2 は優先度低となります。
Control-C などで終了します (^^;;
2.3 簡単な使用例
% utripper abc
'abc' を含むトリップを検索します。
% utripper -i abc
'abc' 'Abc' 'ABc'... のように大文字小文字を区別せずに 'abc' を
含むトリップを検索します。
% utripper -r '^abc'
'abc' を先頭に持つトリップを検索します。
% utripper -r 'abc$'
'abc' を末尾に持つトリップを検索します。
% ./utripper -e '^[0-9]{1,3}GET'
0〜999GET を検索する
% utripper -r '\(.\)\1\1\1\1\1"
6連 (同じ文字が6つ連続して出現) 文字列を検索します。
※ 正規表現が Perl 互換ではないのにご注意。
2.4 基本正規表現と拡張正規表現について
Perl の正規表現になじみが深い方が多いかと思いますが、
このプログラムにリンクされるライブラリの正規表現はいわゆる
POSIX 正規表現で Perl のものとは若干くせが異なるため注意が必要です。
詳しくは参考文献かご利用のシステムの regexec の man などを
参照してください。2.3 の例のように、
- 基本正規表現では `(', `)' は \ でエスケープする必要がある
- \1 のような後方参照は基本正規表現でしか使えない
ことに特に注意してください(ただし、拡張正規表現でも後方参照が
使える正規表現ライブラリもあるようです。Linux の glibc など)。
2.5 その他注意
crypt(3) のアルゴリズム上、末尾の文字には16種類の文字しか
出現しません。これ以外のケースでも、文字列の
指定方法によっては絶対にマッチしないこともありますので、
指定の際には必ずマッチする可能性のあるものを指定してください。
(プログラムであまり熱心にチェックはしていませんので、
コンピュータはずっと必死に見付かるはずのないキーを探し続けます)
絶対にマッチしない例
× utripper -r 'xxx$' (末尾に x は出現しない)
× utripper '@_@' (トリップに出現しない文字が指定された)
2ちゃんねるのトリップは、キーに "<> のいずれかの文字を含むと、
トリップ計算の前にこれらの文字を ", <, > に置き換えて
しまうので出たキーにこれらの文字が含まれていた時には、半角カナの
「シセに変換して利用してください。その他、& や # も変換したほうが
いいのかもしれません。
" → 「 (ただし半角カナ)
< → シ (ただし半角カナ)
> → セ (ただし半角カナ)
プログラムで出力時にこれらの文字に変換しておくこともできるのですが、
半角カナを出力した場合 Un*x 環境だと何かとトラブルが多いのでわざと
変換していません。
3.このプログラムについて
- crypt の計算には Michael Glad 氏の UFC-crypt を改造したものを
利用しています。
- regex.c, regex.h は glibc 2.2.5 のものです。これらの配布条件は
LGPL 2.1 に準拠となりますのでご注意願います。
- MMX 使用ルーチンは UFC-crypt の crypt() 関数を一度コンパイルして
手で修正しています。アセンブラは不慣れなので正しいかどうか
わかりませんが一応動いているようなので問題なしとしています:-)
# 識者の意見をお待ちしています;-)
- 付属の trip.pl に引数としてキーを与えるとトリップを計算します。
チェック用にご利用ください。
- 当然、動作および実行結果に関しては無保証です。
- 動作確認環境 (といっても過去に動かしたことがある、という程度で
動作を保証するわけではありません。)
NetBSD/i386 1.6
FreeBSD/i386 4.4R
RedHat Linux 8.0/i386
Solaris 2.6/sparc (gcc使用)
EWS4800/R4000 (OS バージョン不明(w, gcc 2.95 使用)
4.今後の予定
以下はもうほとんどやる気が無いですが、一応項目だけ...
- 検索状態のセーブ・コンティニュー
- Perl互換な正規表現ライブラリで使えそうなものを物色する
→ PCRE というのがあるようだ。
- ネットワーク分散探索
→ セキュリティとかまで考え出すと大変そう
- john the ripper のソースを調べる
- crack のソースを調べる
- Distributed.net のクライアントを調べる
- その他
5.参考文献
C言語による最新アルゴリズム辞典/奥村晴彦
C MAGAZINE 2001年12月号 (正規表現入門)
6.改版履歴
2001/12/08 第一版
2001/12/09 第二版 (-n オプション追加, 細かい修正)
2001/12/09 第三版 (細かい修正のみ)
2001/12/10 第四版 (Makefile修正のみ)
2001/12/16 第五版
- ソースコードのクリーンアップ
- 検索対象が一文字の場合、-i フラグが無効だったバグを修正
- '-','.' を含むキーを探索対象としていなかったバグを修正
- salt の生成方法を変更。
2002/01/27 第六版
- 連続キーでサーチする時の検索速度の向上 (約10%)
- 検索途中経過表示の変更
- nice値を設定できるオプションを追加 (-p)
2002/10/03 10桁トリップ仮対応
2002/10/27 第七版
- 8to10.pl (旧8桁のログを10桁にコンバートするスクリプト) 添付
- Trip-Mona のルーチンを参考に高速化
- SSE 命令のプリフェッチを試験的に追加
+ (2002/10/28 追加) Cygwin 環境でコンパイルするための調整
2002/11/03 第八版
- 検索ループをちょこっと変更
- glibc から regex (正規表現) 関数を拝借
- キャッシュが小さい場合向けの最適化 (河童セレロンで効果的)
- Mingw32 環境でコンパイルできるようにした
(Cygwin環境で make -fMakefile.mingw でコンパイルできます)
(
geocities.com/tk2001b)