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

2021/05/23(Sun)

[オレオレN6] regex(3)の話は当分終わらないよ

もうみんな(読者0人)飽きたでしょ?未読だけ増えてそろそろお気に入り(気に入ってない)から外したくなってきたでしょ?

でもここは俺のチラシの裏なので書いておかないと忘れることは全部書いておかないとね(ニッコリ)。

@bm(3)のバグのお話

少しは真面目にやれと天井のシミの声がするので真面目にSunday法のペーパーななめ読み、ななめに読むだけ真面目だぞ(当人比)

今回バグが発生した4.1.5 ufastのとこの高速化テクニック、そのままstrstr(3)なりregex(3)で使うには困った問題があるんだな。

ufast
	s = text + patlen - 1;
	e = text + textlen;
ココ →	memset(e, pat[patlen–1], patlen) ;
	while (s < e) {
		k = d0[*s];
		while (k) {
			k=d0[*(s+=k)];
			k=d0[*(s+=k)];
			k=d0[*(s+=k)];
		}
		if (s >= e)
			break;
		match(pat[0..patlen-2], text [s-parlen+1..s-1]);
		s += shift(s, p);
	}
}

おわかりいただけただろうか、 地縛霊が写真に

検索対象文字列のケツに 検索パターン文字列の末尾1文字を含むpatlen分のダミーを埋め込んでるんだよね、つまりオーバーラン前提のガード(sentinel)が必要なロジックってことだ。 ダミーの部分は ゼロフィルされてるので検索パターン文字列の末尾1文字で埋められるのでオーバーランするとk=0なりwhile (k)のループを抜けるということ、そりゃKeithのコードじゃマッチするものがなかった場合ループ抜けられませんわね。

ということで前回はペーパーに存在するバグじゃねえかと書いたが、やっぱりKeithのバグであったごめんねSunday、おのれKeith! *1

でも検索対象文字列の後ろにガード用の領域なんてのはふつーは用意できないよね、const char*で引数にとるstrstr(3)やregex(3)なんかで使うこと考えたらまず不可能。 なもんでKeithは困ってしまって検索対象文字列の最後までufastで検索するのを諦めて、何もマッチしないケースを考えずにeの位置だけズラしてバグったということだな、情状酌量で無罪でいいやnviにはお世話になってるし。

このガードについてペーパー読むと、どんだけここのループで読み飛ばせるかが高速化の秘伝のタレでオーバーランをチェックしないことも隠し味とあるので、前回紹介したN7以降に入ったバグ修正だと性能落ちるのだな。

diff --git a/lib/libc/string/bm.c b/lib/libc/string/bm.c
index e38fe7db6c5..5dc211f8c64 100644
--- a/lib/libc/string/bm.c
+++ b/lib/libc/string/bm.c
@@ -201,7 +201,7 @@ bm_exec(pat, base, n)
 	e = base + n - 3 * pat->patlen;
 	while (s < e) {
 		k = d0[*s];		/* ufast skip loop */
-		while (k) {
+		while (k && s < e) {
 			k = d0[*(s += k)];
 			k = d0[*(s += k)];
 		}

ちなみに4.1.4 fastという実装も紹介されててこいつも検索パターン文字列長分はみ出す前提なのだけど、Nの修正とwhileでのオーバランチェック条件は近い、よって同じくらいの性能劣化になると思われる。

fast
	s = text + patlen - 1;
	e = text + textlen;
	while (s < e) {
		while ((s += d0[*s]) < e) /* skip loop */
			if (s < e+patlen) /* end of text */
				break;
		s -= LARGE;
		match(pat[0..patlen-2], text [s-parlen+1..s-1]);
		s += shift(s, p);
	}

原文だとsをiとtypoしてる箇所があるので修正してある、ところでこのLARGEの説明どこ?(>textlen + patlen)とはあるけど… なんか86年にリリースされた新しいGNU grepへの言及があるからそっちのコード見れば判るのだろうか。

まぁいいや、ペーパーから性能比較の表も引用しておこう。

Algorithm Execution Speed (MB/s) Statistic
i386 sparc mips vax 68k cray step cmp+jump
fast 2.42 6.73 10.92 5.13 3.41 7.68 5.22 202619 (20.3%)
ufast 2.66 7.11 12.52 5.81 4.21 9.21 4.95 213048 (21.3%)

そもそもアンゴルモアの大王降臨前の1991年のことなのでarchが古いわ(sparcをspareとtypoしてるわ)コンパイラも多分ろくな最適化じゃねえだろうから今の環境でもベンチとらんと何とも言えないけど、この程度の差なら許容範囲じゃねえかなこれ… 君らパラノイア過ぎない?

あーめんどくせテストデータ用意して検証しますかね…納期は来世でグアー

kbkさんとこの正規表現メモで正規表現覚えたワイがご本人に記事興味深く~といわれると大学教授の「私この分野素人なのですか(素人ではない)」バトルを感じてツーボールがシュリンクしますね…

@マルチバイトの途中にマッチしてないか前方に戻って探す関数

とりあえず実装した後で考えることにしようか、オレオレCitrusでサポートしてる中に、前に戻ってマルチバイトの先頭を探すことが不可能な文字コードものあったりするとアレなので洗い出ししないとならん。 まぁiconv(3)でしか使われてないモジュールはそもそも実装しないでいいので数も限られるからまず大丈夫だとは思う。

そういえば(その1)、DEC Hanzi(簡体中国語)とDEC Hanyu(繁体中国語)は実装したけどDEC漢字(日本語)って未実装だった、EUCの拡張だけど仕様書どこやったかなぁ。 もうHPとHPEでブーン分社化したあおりなのかTru64UNIXのドキュメントが検索しても出てこないぞ、もうGoogleさんはDECのことなぞ忘れてしまったようで、December + Kanjiばっか引っかかりますね…

ミラーは ここにあることが判った、あとで探す。

そのついででTru64UNIXでサポートされてるExtended ISO-2022-JP(ISO-2022-JPext)というものを発見してしまった。

  • ESC ( B … ASCII
  • ESC $ B … JIS X 0208
  • ESC ( I … JIS X 0201 Katakana
  • ESC $ ( D … JIS X 0212
  • ESC $ ( 0 … UDC

えっナニコレ、まだ異種あったのか壊れるなぁ…

そもそもTru64UNIXのiconv(3)だとISO-2022-JPにも「ESC $ ( 0」のUDCがあるんだな…

そういえば(その2)、VIQRも書き直さないとならん、ほとんど書き終わってたのだが RFC1456に無いモード切替という仕様を発見して憤死したとこまでだっけか…

@POSIX character classのお話

チンPOSIX localeにおいては各locale独自のcharacter classを実装することが許されていて、たとえば日本語localeであれば[:jkanji:]とか[:jhira:][:jkana:]なんてのが許される、*BSDでは未実装だけどglibc2とかSolarisは普通に使えたりする。

そこでふと思ったのだがそろそろ[:emoji:]がPOSIX character classの既定に必要なんじゃねえかなと、実用考えるともっと細分化して

  • [:smile:] … 😀🤣😂😇など
  • [:animal:] … 🐶🐱🙈🙊🙉など
  • [:monster:] … 👹👺👻👽👾🤖など
  • [:linus:] … 🖕 (Linus Torvals Fuck Generatorはこちら)

以下延々と続く、やはりUnicode絵文字は地獄の窯を開いてしまったのである。もうregex(3)にも画像認識技術を組み入れる必要あるんじゃねえのか…

まぁ与太話は置いといて、regex(3)の実装も既定クラスに限定していいなら

typedef struct {
	...
	wctype_t	*types;
	unsigned int	ntypes;
	...
} cset;

なんて不経済な持ち方する必要はなく、以前のcclass.hにあったcitype型を生かして

typedef enum { CALNUM, CALPHA ... } citype;

typedef struct {
	uint32_t types;
#define TALNUM	UINT32_C(1<<CALNUM)
#define TALPHA	UINT32_C(1<<CALPHA)
...
} cset;

みたいにbitmaskのみで持てたのになぁと、メモリも値の追加にかかるコストもぐっと低く実装できるのだが世の中うまくいきませんね…

そうそう、その値の追加についての実装がダルいのだ。Cの暗黒面で不定長配列の操作にいちいちmalloc(3)的なものがダンスするの見苦しいすよね、特にこのwctypeは実用上なら既定の12とプラスlocale固有の数個あれば十分なのに、理論上無限だからね…

やっぱりCにも標準でC++のstd::vector的なtype genericな配列操作ライブラリ欲しいよね、ああ規格に関わってる人はそんな便利なもの増やすよりintmax_tが気になって眠れないですかそうですか…

最近思ったのは、なぜ21世紀にもなってもかように貧困言語のCが生かされてるのか、それはおそらく他の言語実装者が「ね?C言語ってクソでしょ?こっちの言語は甘いよ?」って思わせる為なのではという気がしてきた。 奴隷の鎖自慢というか人は自分より下をみて心の安寧を得るとかパチンコ雑誌に連ちゃんパパが連載されてたとかそういう意味でな… よしチャリティ団体は困窮するlibc実装者に配給物資を今すぐ配るべき、Every 60 seconds a minute passes in Programing Language C. DO SOMETHING!

この手のいわゆるCollection APIって移植性無視するならNにはリストとかキューなら<sys/queue.h>のqueue(3)、ツリーなら<sys/rbtree.h>のrbtree(3)があるのでそいつら使えば楽できるのだけど、type genericな配列は無いのよね。

まぁstd::vectorもマクロで無理矢理に実装できんこともない、たとえばqueue(3)と使い勝手似せてクッソ雑に実装するとこんな感じとか。

#include <errno.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <wctype.h>

#define arraycount(array)	(sizeof(array)/sizeof(array[0]))

static inline int
vector_reserve(void **head, int cached,
    size_t newcapacity, size_t *capacity, size_t size, size_t nmemb)
{
	void *buffer;

	if (newcapacity > *capacity) {
		if (newcapacity > SIZE_MAX / nmemb)
			return ENOMEM;
		if (cached) {
			buffer = malloc(newcapacity * nmemb);
			if (buffer == NULL)
				return ENOMEM;
			memcpy(buffer, (const void *)*head, size * nmemb);
		} else {
			buffer = realloc(*head, newcapacity * nmemb);
			if (buffer == NULL)
				return ENOMEM;
		}
		*head = buffer;
		*capacity = newcapacity;
	}
	return 0;
}

#define VECTOR(name, type, ini) struct name {			\
	type buffer[ini];					\
	type *head;						\
	size_t size;						\
	size_t capacity;					\
}
#define VECTOR_INIT(pv) do {					\
	(pv)->head = &(pv)->buffer[0];				\
	(pv)->size = 0;						\
	(pv)->capacity = arraycount((pv)->buffer);		\
} while (0)
#define VECTOR_UNINIT(pv) do {					\
	if ((pv)->head != &(pv)->buffer[0])			\
		free((pv)->head);				\
} while (0)
#define VECTOR_SIZE(pv)		((pv)->size)
#define VECTOR_CAPACITY(pv)	((pv)->capacity)
#define VECTOR_MAX_SIZE(pv)	(SIZE_MAX / sizeof((pv)->buffer[0]))
#define VECTOR_EMPTY(pv)	(VECTOR_SIZE(pv) == 0)
#define VECTOR_AT(pv, at)	(&(pv)->head[at])
#define VECTOR_FRONT(pv)	VECTOR_AT(pv, 0)
#define VECTOR_BACK(pv)		VECTOR_AT(pv, VECTOR_SIZE(pv) - 1)
#define VECTOR_BEGIN(pv)	((pv)->head)
#define VECTOR_END(pv)		((pv)->head + (pv)->size)
#define VECTOR_NEXT(it)		(it + 1)
#define VECTOR_FOREACH(it, pv)					\
	for (it = VECTOR_BEGIN(pv);				\
	     it != VECTOR_END(pv);				\
	     it = VECTOR_NEXT(it))
#define VECTOR_RBEGIN(pv) ((pv)->head + (pv)->size - 1)
#define VECTOR_REND(pv) ((pv)->head - 1)
#define VECTOR_RNEXT(it)	(it - 1)
#define VECTOR_FOREACH_REVERSE(it, pv)				\
	for (it = VECTOR_RBEGIN(pv);				\
	     it != VECTOR_REND(pv);				\
	     it = VECTOR_RNEXT(it))
#define VECTOR_RESERVE(pv, newcapacity)				\
	vector_reserve((void **)&(pv)->head,			\
	    (pv)->head == &(pv)->buffer[0],			\
	    newcapacity, &(pv)->capacity,			\
	    (pv)->size, sizeof((pv)->buffer[0]))
#define VECTOR_PUSH_BACK(pv, val, ret) do {			\
	if ((pv)->capacity == (pv)->size &&			\
	    (VECTOR_MAX_SIZE(pv) / 2 < (pv)->capacity ||	\
	     VECTOR_RESERVE(pv, (pv)->capacity * 2))) {		\
		ret = ENOMEM;					\
	} else {						\
		(pv)->head[(pv)->size++] = val;			\
		ret = 0;					\
	}							\
} while (0)
#define VECTOR_POP_BACK(pv, val) do {				\
	(pv)->head[--(pv)->size];				\
} while (0)
#define VECTOR_RESIZE(pv, newsize, value) do {			\
	while ((pv)->size < newsize)				\
		VECTOR_PUSH_BACK(pv, value);			\
} while (0)

static const char *cclass_names[] = {
	"alnum",
	"alpha",
	"blank",
	"cntrl",
	"digit",
	"graph",
	"lower",
	"print",
	"punct",
	"space",
	"upper",
	"xdigit",
};

VECTOR(wctype_vector, wctype_t, 10);

struct cset {
	struct wctype_vector types;
};

int
main(void)
{
	struct cset cs;
	size_t i;
	wctype_t type, *elm;
	int ret;
	wint_t c = L'A';

	VECTOR_INIT(&cs.types);
	printf("size: %zd, capacity: %zd\n",
	    VECTOR_SIZE(&cs.types), VECTOR_CAPACITY(&cs.types));
	for (i = 0; i < arraycount(cclass_names); ++i) {
		type = wctype(cclass_names[i]);
		if (type == (wctype_t)0)
			continue;
		VECTOR_PUSH_BACK(&cs.types, type, ret);
		if (ret)
			abort();
	}
	printf("size: %zd, capacity: %zd\n",
	    VECTOR_SIZE(&cs.types), VECTOR_CAPACITY(&cs.types));
	VECTOR_FOREACH(elm, &cs.types)
		printf("%d\n", iswctype(c, *elm));
	VECTOR_UNINIT(&cs.types);
}

ヴォエッ、なんかもう見るだけで胃酸で喉が焼かれる音がしてあっ他の言語使おうってなるな…おのれC言語!

いちおう文字列限定ならば*BSDには<stringlist.h>のstringlist(3)というものがある、作者はいつものフォールリバー大先生。

/*
 * Simple string list
 */
typedef struct _stringlist {
	char    **sl_str;
	size_t    sl_max;
	size_t	  sl_cur;
} StringList;

__BEGIN_DECLS
StringList	*sl_init(void);
int		 sl_add(StringList *, char *);
void		 sl_free(StringList *, int);
char		*sl_find(StringList *, const char *);
int		 sl_delete(StringList *, const char *, int);
__END_DECLS

ただ安全側に倒しるのでsl_add(3)すると文字列コピーが内部で発生するから、ポインタだけでいい時に無駄が多いのがネックであまり使ったことないや。

そんで移植性のあるstd::vectorの代替案だけども、POSIX:2008のopen_memstream(3)を使う手もある。

#include <errno.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <wctype.h>

#define arraycount(array)	(sizeof(array)/sizeof(array[0]))

static const char *cclass_names[] = {
	"alnum",
	"alpha",
	"blank",
	"cntrl",
	"digit",
	"graph",
	"lower",
	"print",
	"punct",
	"space",
	"upper",
	"xdigit",
};

struct cset {
	wctype_t *types;
	size_t ntypes;
};

int
main(void)
{
	struct cset cs;
	FILE *fp;
	char *s;
	size_t n, i, ntypes;
	wctype_t type, *types;
	wint_t c = L'A';

	fp = open_memstream(&s, &n);
	if (fp == NULL)
		abort();
	for (i = 0; i < arraycount(cclass_names); ++i) {
		type = wctype(cclass_names[i]);
		if (type == (wctype_t)0)
			continue;
		if (fwrite(&type, sizeof(type), 1, fp) != 1)
			abort();
	}
	fclose(fp);
	cs.types = (wctype_t *)s;
	cs.ntypes = n / sizeof(wctype_t);
	for (i = 0; i < cs.ntypes; ++i)
		printf("%d\n", iswctype(c, cs.types[i]));
	free(s);
}

fwrite(3)で書き込むんだから当然オブジェクトも許されるし実際に書き込まれる先もchar *なんだからエイリアシング的にもOK(なんならrewindしてfreadすりゃ安心)なのだけど *2、ただまぁopen_wmemstream(3)というワイド文字版があることを考えるとString Builder的なものとしてのみ使用するのが筋かなと。 こういうオブジェクトの書き込みは邪道かなぁと微妙な気分になってしまうのだ。

*1:世界三大Keith、キースリチャーズとキースエマーソンは確定として次点でFreeDesktop.OrgのKeith PackardかCSRGのKeith Bosticで迷いますね。 しゃーない迷ったときはキースへリングにしておこう。
*2:ただしwctype_tは仕様ではscalar typeなのでオブジェクトのポインタであることも許されてるので永続化はできないけどね。 そういえばwctype_tから名前を返すAPIって無いのって片手落ちだよねぇ…

[宗教] ThinkPad X220 3号機が壊れた

なんでX220が3台もあるんだよ壊れてるのはお前だろという話ですがそういえば紹介してなかったね、一昨年オクで知り合って入籍した3人目の妻です、うん本気で気持ち悪いからネタでもやめろ(真顔)。

もちろんX220は1号も2号も健在だしX201もX200sもX61×3もX60sもX40も元気でやってます、240は落として液晶割ってしまいもはや代替部品の入手も難しく困ってる。

あとs30はバッテリの過放電死とパームレストの加水分解だけでなく、液晶の偏光板にヴィネガーシンドローム出てきた。 まぁ予備が1枚押入ひっくり返せば出てくるはずなのでまたいずれ…昔からパラノイアなもんで必ず一台組めるくらいのスペアパーツ用意してたからな…

話を戻して3号機の件だけど、急に今朝からキーボード入力がおかしくなって操作不能になってしまった。 だいぶキーボードヘタってたせいもあるけど、元々システムボードも不安定なとこあったからそっちの問題かもしれない。

昔は最低1枚はキーボードとシステムボードの予備を確保してたのだけど、貧困なので最近はサボってたからさぁ困った、妻を泣かせる甲斐性なしの夫でごめんね…(本気で気持ち悪い)

つーかそもそも予備として買った3号機をメインで使ってること自体何かがおかしかったのだが、スタックをポップしかできないかわいそうな脳味噌だからちかたないね。

まぁ日本語キーボードがどっか探せば1枚はあるはずなので、そいつでどっちの問題かテストしますかね。 なるべく1号2号からひっぺがすとか付喪神の嫉妬の元なのでやりたくない。

システムボード逝ってたらどうしようかなぁ、あえてX230のシステムボード中古で買って7列キーボード改造するのもアリか…

とりあえずいったん開発環境をX201に戻したのだけど、クリーンインストールした20H1がなぜかDNS lookupが不調で困る、どうもAAAAレコードが返ってくるとAレコードをみずにhostname lookup failureになるっぽいのだがよくわからん。対策としては一度PowerShell立ち上げてnslookupすると成功しキャッシュされるのでブラウザとかCygwinが正常に動くようになる…なんじゃこりゃ。