Not only is the Internet dead, it's starting to smell really bad.:2021年05月18日分

2021/05/18(Tue)

[オレオレN6] わからない俺は雰囲気でregex(3)のコードを弄っている(その4)

前回はFがHenry Spencer's regexに追加したBM法による文字列検索のコードの設計が酷いって話をしたところで、なんか使い回しの効く実装にしてなんならstrstr(3)やwcswcs(3)みたいにlibcで使えると便利なのかなと思ってたのだが、 このstrstr/wcswcsのマニュアルのSEE ALSOには載ってないんだけど、メムメムことmemmem(3) *1の方に、bm(3)という項目があるのに気づいたゾ。

NAME
     bm_comp, bm_exec, bm_free -- Boyer-Moore string search

LIBRARY
     Standard C Library (libc, -lc)

SYNOPSIS
     #include <sys/types.h>
     #include <bm.h>

     bm_pat *
     bm_comp(u_char *pattern, size_t patlen, u_char freq[256]);

     u_char *
     bm_exec(bm_pat *pdesc, u_char *text, size_t len);

     void
     bm_free(bm_pat *pdesc);

はえー移植性はアレやけどもBM法による文字列検索関数ってすでに実装あったのね。

まぁスキップテーブルなんて大したサイズじゃないのにmalloc/freeが必要なI/Fは気に入らんけど。 ふつうにstrstr(3)やwcswcs(3)と同じI/Fで実装できるはずなのでちょっと無駄に複雑だなあという。

なおマニュアルにHISTORYの項が無いので由来が判らん、コード書いたのはCSRGのKeith BosticでCOPYRIGHTの日付見る限り4.4BSD Lite由来ぽいのだけど、いつもの Ancient UNIX Archiveには存在しないんだよな、なんでNにだけ生えてるのかよく判らんなこれ。

ちなみにNからforkしたOではこのbm(3)、かつて要らねえもんは全部消すって大掃除やった時にタゲられたようで 消されとるね。

つーことでregex(3)のコードもこいつ使って書き直せばいいじゃんって感じなんやな、あの クソデカ差分なんか必要なくて、bm(3)とmemmem(3)だけで書き直せるからばずいぶんとスッキリするよね、まぁどっちも移植性無いけどさ。

まぁワイの今いじってるwide string regexにはbm(3)はそのまま使えないし、memmem(3)のワイド文字版のwmemmem(3)も無いのだけど、まぁI/Fをこいつらに合わせて新規に書けばいい話である。

ちなみにこのbm(3)の作者であるKeith Bosticはnviの作者でもあるんだけど、今回ワイが弄ってるnvi-1.81とかnvi2ってのは 彼の最終版であるnvi-1.79をforkして勝手に後継名乗ってるだけなんだよね、なので俺が正規表現周りのバグ潰した後にnvi3とかnvi-114514とか名乗っても問題ないのだが、他人の王冠を被る趣味は無いし王になったところで断頭台の露と消え銀の盆の上に頭が乗るだけなのだ。

それにしてもまたnvi-1.81のコード弄ってると、かつて初見のコードに苦労しつつなんとかmultibyte localeで動作するまで直した後、そんなことよりnvi-m17nのUTF-8対応マダー?(チンチン)とか言われて、ああ俺のやってる作業なんて誰も求めてねえのだなぁと悟りを開いたのを思い出して気分が荒みますね。

*1:個人的にlibc関数の中で声に出して読みたい名前第一位である

[オレオレN6] わからない俺は雰囲気でregex(3)のコードを弄っている(その5)

ということで先にnviでなくlibcの方のregex(3)からF由来のBM法コードを除去して、libcのbm(3)を使うように修正してみたコード。

diff --git a/lib/libc/regex/engine.c b/lib/libc/regex/engine.c
index 06d9c251ee..d227f748a4 100644
--- a/lib/libc/regex/engine.c
+++ b/lib/libc/regex/engine.c
@@ -130,13 +130,6 @@ matcher(struct re_guts *g, const char *string, size_t nmatch,
 	const char *start;
 	const char *stop;
 	int error = 0;
-	/* Boyer-Moore algorithms variables */
-	const char *pp;
-	size_t cj, mj;
-	const char *mustfirst;
-	const char *mustlast;
-	size_t *matchjump;
-	size_t *charjump;
 
 	_DIAGASSERT(g != NULL);
 	_DIAGASSERT(string != NULL);
@@ -158,46 +151,13 @@ matcher(struct re_guts *g, const char *string, size_t nmatch,
 
 	/* prescreening; this does wonders for this rather slow code */
 	if (g->must != NULL) {
-		if (g->charjump != NULL && g->matchjump != NULL) {
-			mustfirst = g->must;
-			mustlast = g->must + g->mlen - 1;
-			charjump = g->charjump;
-			matchjump = g->matchjump;
-			pp = mustlast;
-			for (dp = start+g->mlen-1; dp < stop;) {
-				/* Fast skip non-matches */
-				while (dp < stop && charjump[(int)*dp])
-					dp += charjump[(int)*dp];
-
-				if (dp >= stop)
-					break;
-
-				/* Greedy matcher */
-				/* We depend on not being used for
-				 * for strings of length 1
-				 */
-				while (*--dp == *--pp && pp != mustfirst);
-
-				if (*dp == *pp)
-					break;
-
-				/* Jump to next possible match */
-				mj = matchjump[pp - mustfirst];
-				cj = charjump[(int)*dp];
-				dp += (cj < mj ? mj : cj);
-				pp = mustlast;
-			}
-			if (pp != mustfirst)
-				return REG_NOMATCH;
-		} else {
-			for (dp = start; dp < stop; dp++)
-				if (*dp == g->must[0] &&
-				    (size_t)(stop - dp) >= g->mlen &&
-				    memcmp(dp, g->must, (size_t)g->mlen) == 0)
-					break;
-			if (dp == stop)		/* we didn't find g->must */
-				return REG_NOMATCH;
-		}
+		if (g->pdesc != NULL)
+			dp = (const char *)bm_exec(g->pdesc,
+			    (u_char *)__UNCONST(start), stop - start);
+		else
+			dp = memmem(start, stop - start, g->must, g->mlen);
+		if (dp == NULL)		/* we didn't find g->must */
+			return REG_NOMATCH;
 	}
 
 	/* match struct setup */
diff --git a/lib/libc/regex/regcomp.c b/lib/libc/regex/regcomp.c
index 8b2101db2a..9fe4c8e13f 100644
--- a/lib/libc/regex/regcomp.c
+++ b/lib/libc/regex/regcomp.c
@@ -38,6 +38,7 @@
 #include <sys/types.h>
 
 #include <assert.h>
+#include <bm.h>
 #include <ctype.h>
 #include <limits.h>
 #include <stdio.h>
@@ -105,8 +106,6 @@ static int enlarge(struct parse *, sopno);
 static void stripsnug(struct parse *, struct re_guts *);
 static void findmust(struct parse *, struct re_guts *);
 static int altoffset(sop *, int);
-static void computejumps(struct parse *, struct re_guts *);
-static void computematchjumps(struct parse *, struct re_guts *);
 static sopno pluscount(struct parse *, struct re_guts *);
 
 static char nuls[10];		/* place to point scanner in event of error */
@@ -144,9 +143,6 @@ static int never = 0;		/* for use in asserts; shuts lint up */
 #define	never	0		/* some <assert.h>s have bugs too */
 #endif
 
-/* Macro used by computejump()/computematchjump() */
-#define MIN(a,b)	((a)<(b)?(a):(b))
-
 #define	RECLIMIT	256
 
 /*
@@ -213,8 +209,7 @@ regcomp(regex_t *preg, const char *pattern, int cflags)
 	g->neol = 0;
 	g->must = NULL;
 	g->moffset = -1;
-	g->charjump = NULL;
-	g->matchjump = NULL;
+	g->pdesc = NULL;
 	g->mlen = 0;
 	g->nsub = 0;
 	g->backrefs = 0;
@@ -237,14 +232,8 @@ regcomp(regex_t *preg, const char *pattern, int cflags)
 	/* only use Boyer-Moore algorithm if the pattern is bigger
 	 * than three characters
 	 */
-	if (g->mlen > 3) {
-		computejumps(p, g);
-		computematchjumps(p, g);
-		if (g->matchjump == NULL) {
-			free(g->charjump);
-			g->charjump = NULL;
-		}
-	}
+	if (g->mlen > 3)
+		g->pdesc = bm_comp((u_char *)__UNCONST(g->must), g->mlen, NULL);
 	g->nplus = pluscount(p, g);
 	g->magic = MAGIC2;
 	preg->re_nsub = g->nsub;
@@ -1725,138 +1714,6 @@ altoffset(sop *scan, int offset)
 	return largest+offset;
 }
 
-/*
- - computejumps - compute char jumps for BM scan
- *
- * This algorithm assumes g->must exists and is has size greater than
- * zero. It's based on the algorithm found on Computer Algorithms by
- * Sara Baase.
- *
- * A char jump is the number of characters one needs to jump based on
- * the value of the character from the text that was mismatched.
- */
-static void
-computejumps(struct parse *p, struct re_guts *g)
-{
-	int ch;
-	size_t mindex;
-
-	_DIAGASSERT(p != NULL);
-	_DIAGASSERT(g != NULL);
-
-	/* Avoid making errors worse */
-	if (p->error != 0)
-		return;
-
-	assert(NC < MEMLIMIT(*g->charjump));
-	g->charjump = malloc((NC + 1) * sizeof(*g->charjump));
-	if (g->charjump == NULL)	/* Not a fatal error */
-		return;
-	/* Adjust for signed chars, if necessary */
-	g->charjump = &g->charjump[-(CHAR_MIN)];
-
-	/* If the character does not exist in the pattern, the jump
-	 * is equal to the number of characters in the pattern.
-	 */
-	for (ch = CHAR_MIN; ch < (CHAR_MAX + 1); ch++)
-		g->charjump[ch] = g->mlen;
-
-	/* If the character does exist, compute the jump that would
-	 * take us to the last character in the pattern equal to it
-	 * (notice that we match right to left, so that last character
-	 * is the first one that would be matched).
-	 */
-	for (mindex = 0; mindex < g->mlen; mindex++)
-		g->charjump[(int)g->must[mindex]] = g->mlen - mindex - 1;
-}
-
-/*
- - computematchjumps - compute match jumps for BM scan
- *
- * This algorithm assumes g->must exists and is has size greater than
- * zero. It's based on the algorithm found on Computer Algorithms by
- * Sara Baase.
- *
- * A match jump is the number of characters one needs to advance based
- * on the already-matched suffix.
- * Notice that all values here are minus (g->mlen-1), because of the way
- * the search algorithm works.
- */
-static void
-computematchjumps(struct parse *p, struct re_guts *g)
-{
-	size_t mindex;		/* General "must" iterator */
-	size_t suffix;		/* Keeps track of matching suffix */
-	size_t ssuffix;		/* Keeps track of suffixes' suffix */
-	size_t *pmatches;	/* pmatches[k] points to the next i
-				 * such that i+1...mlen is a substring
-				 * of k+1...k+mlen-i-1
-				 */
-
-	_DIAGASSERT(p != NULL);
-	_DIAGASSERT(g != NULL);
-
-	/* Avoid making errors worse */
-	if (p->error != 0)
-		return;
-
-	if (g->mlen > MEMLIMIT(*pmatches) ||
-	    (pmatches = malloc(g->mlen * sizeof(*pmatches))) == NULL) {
-		g->matchjump = NULL;
-		return;
-	}
-
-	if (g->mlen > MEMLIMIT(*g->matchjump) ||
-	    (g->matchjump = malloc(g->mlen * sizeof(*g->matchjump))) == NULL) {
-		/* Not a fatal error */
-		free(pmatches);
-		return;
-	}
-
-	/* Set maximum possible jump for each character in the pattern */
-	for (mindex = 0; mindex < g->mlen; mindex++)
-		g->matchjump[mindex] = 2 * g->mlen - mindex - 1;
-
-	/* Compute pmatches[] */
-	for (suffix = mindex = g->mlen; mindex-- > 0; suffix--) {
-		pmatches[mindex] = suffix;
-
-		/* If a mismatch is found, interrupting the substring,
-		 * compute the matchjump for that position. If no
-		 * mismatch is found, then a text substring mismatched
-		 * against the suffix will also mismatch against the
-		 * substring.
-		 */
-		while (suffix < g->mlen
-		    && g->must[mindex] != g->must[suffix]) {
-			g->matchjump[suffix] = MIN(g->matchjump[suffix],
-			    g->mlen - mindex - 1);
-			suffix = pmatches[suffix];
-		}
-	}
-
-	/* Compute the matchjump up to the last substring found to jump
-	 * to the beginning of the largest must pattern prefix matching
-	 * it's own suffix.
-	 */
-	for (mindex = 0; mindex <= suffix; mindex++)
-		g->matchjump[mindex] = MIN(g->matchjump[mindex],
-		    g->mlen + suffix - mindex);
-
-	ssuffix = pmatches[suffix];
-	while (suffix < g->mlen) {
-		while (suffix <= ssuffix && suffix < g->mlen) {
-			g->matchjump[suffix] = MIN(g->matchjump[suffix],
-			    g->mlen + ssuffix - suffix);
-			suffix++;
-		}
-		if (suffix < g->mlen)
-			ssuffix = pmatches[ssuffix];
-	}
-
-	free(pmatches);
-}
-
 /*
  - pluscount - count + nesting
  */
diff --git a/lib/libc/regex/regex2.h b/lib/libc/regex/regex2.h
index 3d2fb69240..d63f920b9f 100644
--- a/lib/libc/regex/regex2.h
+++ b/lib/libc/regex/regex2.h
@@ -149,8 +149,7 @@ struct re_guts {
 	size_t neol;		/* number of $ used */
 	char *must;		/* match must contain this string */
 	int moffset;		/* latest point at which must may be located */
-	size_t *charjump;	/* Boyer-Moore char jump table */
-	size_t *matchjump;	/* Boyer-Moore match jump table */
+	bm_pat *pdesc;		/* for Boyer-Moore string search, see bm(3) */
 	size_t mlen;		/* length of must */
 	size_t nsub;		/* copy of re_nsub */
 	int backrefs;		/* does it use back references? */
diff --git a/lib/libc/regex/regexec.c b/lib/libc/regex/regexec.c
index 9aa0a14bf5..ac841c1abd 100644
--- a/lib/libc/regex/regexec.c
+++ b/lib/libc/regex/regexec.c
@@ -45,6 +45,7 @@
 #include <sys/types.h>
 
 #include <assert.h>
+#include <bm.h>
 #include <ctype.h>
 #include <limits.h>
 #include <stdio.h>
diff --git a/lib/libc/regex/regfree.c b/lib/libc/regex/regfree.c
index 4e9ef36178..19ed2f02d6 100644
--- a/lib/libc/regex/regfree.c
+++ b/lib/libc/regex/regfree.c
@@ -38,6 +38,7 @@
 #include <sys/types.h>
 
 #include <assert.h>
+#include <bm.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <regex.h>
@@ -73,5 +74,7 @@ regfree(regex_t *preg)
 	free(g->sets);
 	free(g->setbits);
 	free(g->must);
+	if (g->pdesc != NULL)
+		bm_free(g->pdesc);
 	free(g);
 }

とりあえずtest/lib/libc/regex/以下のテストコードは問題なく動いてる感じだけど、性能に差があったりするとbm(3)の方にチューニングかけないとならんなぁ。 でもやっぱりテストデータ準備するのめんどくさいから当面放置かな。

[オレオレN6] わからない俺は雰囲気でregex(3)のコードを弄っている(その6)

さっきの差分書いててbm_comp(3)の第3引数にてきとーにNULL指定したけど、結構重要なパラメーターなんだな。

/* 
 * 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,
};

文字の出現頻度データベースなんだが、ご覧の通りen_US.US-ASCIIとかいう田舎者向けのテーブルなので、GR領域の頻度がすべてゼロになっとる。

こまったなこれ、同じシングルバイトなlocaleであってもGLの方が使用頻度高い言語の方が多いわけでな、どんだけ性能に悪影響出るんだろう。 俺が眺めたBM法のペーパーにはこんなの無かったはずだから改良法なんだろうけど。

これなのかな、 文字の出現頻度を考慮した文字列検索アルゴリズムの提案、よくわからないもうワイの脳は縮小しているのでなにもわからない。

これ真面目に考えるとlocale毎に用意する必要があるので、なんならLC_CTYPEの仕様を拡張してテーブル持つ必要があるわけだなぁ。 ワイド文字だといちいち全部の文字に順位つけたらUnicodeとかGB18030で巨大な定義が出来上がってしまうので、上位99文字だけlocaledbに持って順位を返す関数がwctype.hあたりに必要ってこと。

そんで最大の問題は各言語毎の頻度データを作る作業なんやな、ワイは言語学者でもビッグデータ屋でもねえただの暇人なのでコーパスとか持ってねえからなぁ。 よく ジミーウェールズのメッセージを読むサイトのダンプをコーパスにして自然言語処理なんて記事があるけど、ライセンス的にどうなるのかあのめんどくせえCC-BYなんちゃらの文章読みたくないからな。 クローラーで収集するっても迷惑だし著作権法的にグレーだし良いことないしな。

まぁやっぱりbm(3)とは別にこの改良法を必要としない実装も用意するんですかね、それはそれでもったいない気もするけど。

あとI/Fもconstじゃなかったり、あとbm_compで無駄な検索文字列のコピーが発生してたり(ポインタだけ持つかbm_execで検索文字列渡す方がいい)で。改めて関数用意した方が良さそうかな。

bm_pat *
bm_comp(pb, len, freq)
	u_char const *pb;
	size_t len;
	u_char const *freq;
{
...
	if ((pat->pat = malloc(pat->patlen)) == NULL)
		goto mem;
	memcpy(pat->pat, pb, pat->patlen);