○[オレオレN6] 続々・bm(3)のバグのお話
前回はHume-Sunday法
*1のペーパーを紐解いて、4.1.5 ufast loopによるパラノイアじみた高速化手法(ただし実用性は薄い)を完全に理解した、多分明日には忘れてるが。
その結果本家のN7以降に入った修正は大間違いで(通常運行)いまだオーバーラン問題を抱えていることが判明したのでいつも通りﾊﾞｰﾔﾊﾞｰﾔと煽り倒した後、オレオレN6では
ufast loopを使わない正しい修正を入れたとこまでだったっけ。
さてお次、やはりHume-Sunday法におけるBM法の改良点である 4.2.4 guard の項を読み解くことにする、ペーパーの実証コードでは
register ro = pat.rareoff, rc = pat.rarec;
…
if(s[ro] != rc) /* guard test */
goto mismatch;
とある部分、ぱっと見ただけでro == pat.rareoffが正の値であれば、こいつもオーバーランする可能性があるなぁというパラノイア。
その不安を潰すべく理論は後回しにしてpat.rareoffの計算部分を読んでみることにしようかね。
1 static struct
2 {
3 int patlen;
4 unsigned char pat[1024];
5 ...
6 int rarec, rareoff;
7 ...
8 } pat;
9
10 void prep(unsigned char *pb, int len)
11 {
12 register unsigned char *pe;
13 ...
14
15 memcpy(pat.pat, pb, pat.patlen) ; /* store pattern */
16 ...
17 /* get guard */
18 r = 0 ;
19 for (pb = pat.pat, pe = pb + pat.patlen - 1; pb < pe; pb++)
20 if(freq[*pb] < freq[pat.pat[r]])
21 r = pb - pat.pat;
22 pat.rarec = pat.pat[r];
23 pat.rareoff = r - (pat.patlen–1);
24 ...
25 }
はい、21,23行目をみれば一目瞭然だけどpat.rareoffは必ず負の値になる、ということでここでのオーバーランは無いという事で安心してよい。
負の値だからアンダーランの可能性もあるけど、これは検索開始位置が
int exec(unsigned char *base, int n)
{
register unsigned char *s;
s = base + pat.patlen - 1;
とpat.patlen - 1足された位置からのスタートなのでこれも心配せずともよろしい。
ただしpat.rareoffについてはモダンなプログラムであればintではなくptrdiff_tで宣言すべきではある、しかし前回も書いた通りstruct bmpatがpublicで宣言されてるのでもはやintから変更できないのだ。
よって検索パターン文字がINT_MAXより長かったりするとinteger overflowが起きる可能性はありますわね、まぁ変えるとABI/API壊れるのでちかたないね、考えないことにする。
よしもうどうでもいいな(セキュリティ厨)、寝るぞ！
…また壁の人を塗り込めたようなシミから5Gで脳に直接苦情が届いたので、このrareoffとrarecってなんなのよというとこを今度は見ていくよ。
まず19行目で検索パターン文字の先頭から末尾-1までループしつつ、20行目でfreqというテーブルを参照しにいってる。
このfreqってのはペーパー中に実装は示されておらず、freq.hとしてincludeしてるよーと存在を仄めかされてるだけなのだが、
過去回でちょこっと紹介した文字の出現頻度テーブルだ、bm(3)での実装は以下の通り。
/*
* XXX
* The default frequency table starts at 99 and counts down. The default
* table should probably be oriented toward text, and will necessarily be
* locale specific. This one is for English. It was derived from the
* OSF/1 and 4.4BSD formatted and unformatted manual pages, and about 100Mb
* of email and random text. Change it if you can find something better.
*/
static u_char const freq_def[256] = {
0, 0, 0, 0, 0, 0, 0, 0,
0, 77, 90, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
99, 28, 42, 27, 16, 14, 20, 51,
66, 65, 59, 24, 75, 76, 84, 56,
72, 74, 64, 55, 54, 47, 41, 37,
44, 61, 70, 43, 23, 53, 49, 22,
33, 58, 40, 46, 45, 57, 60, 26,
30, 63, 21, 12, 32, 50, 38, 39,
34, 11, 48, 67, 62, 35, 15, 29,
71, 18, 9, 17, 25, 13, 10, 52,
36, 95, 78, 86, 87, 98, 82, 80,
88, 94, 19, 68, 89, 83, 93, 96,
81, 7, 91, 92, 97, 85, 69, 73,
31, 79, 8, 5, 4, 6, 3, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
};
うん0x20 SPACEさいつよですね、そらそうか。
つまりはだ、19～20行目でやってる事は
- pat.rarec … 最も出現頻度の低い文字かつ末尾から一番近いもの
- pat.rareoff … ↑の末尾からの距離
を導き出す処理だということが判る。
ではもう一度このrarec/rareoffの使われてる部分のコードを読んでみよう。
1 register ro = pat.rareoff, rc = pat.rarec;
2 s = base+pat.patlen–1;
3 e = base+n;
4 ep = pat.pat + pat.patlen–1
5
6 …
7 if(s[ro] != rc) /* guard test */
8 goto mismatch;
9 for(p = pat.pat, q = s–n1; p < ep; ){ /* fwd match */
10 if(*q++ != *p++)
11 goto mismatch;
12 }
この7～8行目の処理をよーく見てみよう。
勘のいい人はもう気づきましたよね？この7～8行目のコード、文字の出現頻度なんて完全に無意味なのですわ。
単に9～10行目のループに入る前に、適当な一文字だけピックアップして一致するかをチェックしてるだけなのよね。
なので別にこれ
if(s[-n1] != *pat.pat) /* guard test */
goto mismatch;
と書き換えても同じなんだよね…
前回のbm(3)のリファクタリングにより、9～10行目の処理は
/* guard test */
if (s[pat->rareoff] != pat->rarec ||
/* fwd match */
memcmp(pat->pat, s - n1, n1))
goto mismatch;
と書き直せるよといったけど、さらに追加でこう書き直してもいいわけだ。
/* guard test */
if (s[-n1] != *pat.pat ||
/* fwd match */
memcmp(pat->pat, s - n1, n1))
goto mismatch;
これCで文字列定数との比較を行う場合、strcmp(3)にかかるコストを嫌って
const char *s = ...
if (!strcmp(s, "unko"))
...
を
const char *s = ...
if (*s == 'u' && !strcmp(s, "unko"))
...
と書き換えてまず先頭の一文字がマッチしてるかを確認した上で、改めてstrcmp(3)を呼んで関数呼び出しのコストをなるべく省くなんてテクニックありますよね。
それとおんなじでループになるべく入らないようにするってだけの、パラノイアックな高速化テクニックってだけよねこれ…
まじで「はぁ？」って声出ちゃったよ俺、これLC_CTYPEに文字の使用頻度を持つテーブルが必要だなぁとか考えてた俺馬鹿みたいじゃん、まぁ馬鹿は間違ってないが…
一番かわいそうなのはちゃんと真面目にfreqテーブルを作ったKeith Bosticですかねぇ、まぁちゃんと論文読まなかったのが悪いのだが。
ということでもうbm_comp(3)の第3引数要らねえよなこれって結論に達しつつあるのだが、何か俺が見逃してる事があればそっと5G電波でワイの脳に直接送信してくださいね📶
(追記) 見逃してました、
フォローアップ読んでね💛
@次回予告
さて多分最終回、ミスマッチの場合に読み飛ばす移動距離としてpat.md2というパラメーターがあるのだが、通常BM法ではsuffix ruleというテーブルを引いて移動距離を決めるのだけど、Hume-Sunday法では一意に決まっていることが高速化に寄与している。
その原理を読み解いていこうかと。
あと余裕があれば、bm(3)には実装されていないのだけどpat.loopoffsetというパラメーターがあって、これを事前に計算しておくことで検索パターン文字列と検索対象文字列の比較する長さを減らせるみたいなのだ。
なんかペーパーの信用度が個人的にガッツリ落ちてるので、実は計算するとコストは変わらない的なオチが待ってんじゃねぇのという疑惑を抱いてしまうが、そこも読んでいきたい。