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

2021/05/01(Sat)

[WWW] アクセシビリティ

久米田康治作品ファンならそらワイと同じパラノイアで「勝手にマイニングさせるマルウェアに絶望した!」と叫びながらJavaScript常時オフにするの当り前じゃねーのという話かと思ったらぜんぜん違った、至極まっとうなアクセシビリティやアーカイビングに関する話で、スクリプト無効警察とかいってる連中は最低限文化的過ぎませんかね。

そういう連中には<●> <●>って目してスコップ片手に「ああ!もうJavaScript必須だとイライラするの!」と言いながらジュース注射したり生肉押しつけたりカサブタ剥がしたりする本物の警察ってやつをお見せすればいいのか、最後だけ別人の気がするがまぁ同じようなもんだ。

なお当チラシの裏はCookie使わんしJavaScriptはソースコードのシンタックスハイライトと写真拡大表示にしか使ってないし、これも近日サーバーサイドで対応することで廃止予定なのでパラノイアでも安心してアクセスいただけます、なんせ書いてる本人がパラノイアだからな。

アーカイビングの話で思い出したが、うちにひっきりなしにアクセスしに来るRSSリーダー特にfeedlyなのだが、あんだけストーカーが如く執拗に数分毎に新着記事取得しにクローラーやってくるのに、過去記事の内容に訂正や追記があっても一切更新しないんだよな(inoreaderはする)。 この当チラシの裏は報われることの無かったソースコードの地縛霊がワイの体を借りて自動筆記してるもので、推敲とか一切することなく数分で書き上げるフリースタイルラップバトル形式なので後から解読不能な文章はさすがに訂正いれることも多いのよね。 先日も菊紋(やんごとなき家紋)を菊門(尻の穴の俗称)と悪意なくナチュラルに誤変換して時代が時代なら不敬で死体が転がるとこで気づいてすぐさま訂正したのだが、feedlyには誤字のままアーカイブされとってこれ会社潰れるまで残るんだろうなぁ。

でもこれはRSSの思想からすると、過去記事の修正追加が発生したらそれは改めて更新情報として新記事として配信すべきなんだろうね。 でも頻繁に同じタイトルの新着が数分おきに流てくるようになったら、今度はさぞや皆さん僕の事ウザい~だろ(ハーヨイヨイ)なので、落としどころがおもいつかん。 全文配信を止めるって手もあるけど、こんな検索性も悪くその上狂った文章書くサイトに直接アクセスしてIPアドレス残したくない人には申し訳ないし。

2021/05/04(Tue)

[オレオレN6] lint(1)を削除した

そのうちやろうと思ってた表題の作業だけど、別件作業中にrestrict修飾子がらみでlint(1)由来のトラブル起きたのでカッとなって先に殺すことにした、誰でもよかった。 コミットログ

こちらがlint(1)ありでbuild releaseにかかった時間

make release started at:  Tue May  4 01:45:24 JST 2021
make release finished at: Tue May  4 04:07:18 JST 2021
===> Successful make release
===> build.sh ended:      Tue May  4 04:07:18 JST 2021
===> Summary of results:
         build.sh command:    ./build.sh -j 8 release
         build.sh started:    Tue May  4 01:45:23 JST 2021
         NetBSD version:      6.1_STABLE
         MACHINE:             amd64
         MACHINE_ARCH:        x86_64
         Build platform:      NetBSD 6.1_STABLE amd64
         HOST_SH:             /bin/sh
         TOOLDIR path:        /usr/tooldir
         DESTDIR path:        /usr/src/obj.amd64/destdir.amd64
         RELEASEDIR path:     /usr/src/obj.amd64/releasedir
         Updated makewrapper: /usr/tooldir/bin/nbmake-amd64
         Successful make release
         build.sh ended:      Tue May  4 04:07:18 JST 2021
===> .
 8515.21s real  7474.41s user  2144.04s system

そんでこちらがlint(1)抹殺後。

make release started at:  Tue May  4 04:13:03 JST 2021
make release finished at: Tue May  4 06:28:52 JST 2021
===> Successful make release
===> build.sh ended:      Tue May  4 06:28:52 JST 2021
===> Summary of results:
         build.sh command:    ./build.sh -j 8 release
         build.sh started:    Tue May  4 04:13:02 JST 2021
         NetBSD version:      6.1_STABLE
         MACHINE:             amd64
         MACHINE_ARCH:        x86_64
         Build platform:      NetBSD 6.1_STABLE amd64
         HOST_SH:             /bin/sh
         TOOLDIR path:        /usr/tooldir
         DESTDIR path:        /usr/src/obj.amd64/destdir.amd64
         RELEASEDIR path:     /usr/src/obj.amd64/releasedir
         Updated makewrapper: /usr/tooldir/bin/nbmake-amd64
         Successful make release
         build.sh ended:      Tue May  4 06:28:52 JST 2021
===> .
 8150.35s real  7303.46s user  2044.78s system

まぁ誤差レベルっすね、lint(1)自体はそれほどビルド時間に影響を及ぼすほどのものでは無かったちゅーことで。 ただまぁfalse alarmによって無駄に開発者の労力を奪ってきたのだから殺しても正当防衛であることを主張する。

いまどきbuild releaseごときに2時間半かかる哀れな開発環境のログを貼り人生の敗残者っぷりを晒しておりますが、今時なら64コア128スレッドにNVMeストレージで10分もかからんで終わるんかのう。まぁ新マシンなら来世で調達するわ。

さてお次はN6のgcc4.5.3はさすがにいろいろ厳しいし、本家Nですらgcc10になる時代なのでそこらへんのアップデートかなぁ、あ、それより先にlibmアップデートせんとC++関連でいまほんとビルド通らないアプリ多過ぎる件やな…つーかCMake依存しとるやつが全滅ほんとひで。

2021/05/11(Tue)

[自宅ネットワーク管理者] HPE OfficeConnect 1820セットアップ完了

ようやっとやる気出して設定したよ、設定自体は数分もかからず終わる作業だけど設置場所の確保と配線がね…しばらく前に16Uラック処分しちゃったのでな。

家に16Uラックあったとかいうと自宅をデータセンターと勘違いしたいわゆる誤家庭と思われそうだが、音楽やってた頃のラックマウントタイプの音源やらエフェクターやら格納用に買ったものでそっちの趣味は無い。 というか誤家庭って48Uラックが最低一本無いと名乗れないはずだよね、あと電源工事。

まず外見だけど、ProcurveブランドからOfficeConnectブランドに変わってグレー一色のクッソ地味なデザインになったのでマジで新しい玩具買ったワクワク感ゼロすね。

そんで起動時のテストパターンも安物スイッチにありがちなステータス表示のLEDが各ポートのRJ45コネクタでなく一か所に並んでるタイプでとても地味、なのでテストパターン見たさに何度も再起動する気すら起きないマジで実用品。 やっぱLEDが各ポート直付けでないスイッチって直感的じゃないから一瞬戸惑うね、まぁコストダウンの為だから嫌ならもっと上位機種買えってなんだろうけど、そうするとファンレスじゃないからな。

それとやっぱしシリアルコンソールやssh経由でのCLI設定ができない機種は使い勝手いまいちね、安全のためにWebUIを無効にする事ができない(そら設定手段がそれ唯一だし)ので、ネットワーク管理者以外からアクセスできないようにするにはVLAN切って隔離する必要があるのがもったいない。 とはいえこの手のファイアウォールも無いL2スイッチを直接外部ネットワークに晒す阿呆もおらんだろうからWebUI無効にする需要もあまり無いのだろう、つーかしたけりゃやっぱり上位機種買えってこった。

まぁセキュリティ面からCLI onlyにしたいという理由でなければ、ProcurveのCLIと同じ操作性でWebUIをPython Scriptで操作する hp1820-cliというツールを書いた人がいるようなのでそれ使えばいいんじゃないかな、ワイはセキュリティ面でWebUI無効にしたいだけなのでこれ使う意味は無いから動作確認はしていない。

そんでWebUIはHTTPを無効にはできない上にHTTPSはデフォルト無効、HTTPSを有効にするとHTTPは非特権モードで特権モードはHTTPS接続にのみ許可される、パラノイアなら有効にしといた方がいいかな。 オレオレ証明書でよければSecure HTTP Configuration->Certificate Statusの横にある歯車ボタン押すだけでsha256RSA(2048bit)というまぁ今でも実用に耐える強度の証明書を生成して配備してくれるもよう。

しかし困ったことに接続がいまどきTLS1.0 onlyなのよな、TLS1.2以降を使うようにする設定項目も無いっぽいので今時のブラウザだと警告でて表示できんのだ、この問題はリリースノートにもそれらしき事書いてあるな。

Version 02.11
WebUI
CR_254616
Symptom/Scenario: When using the Chrome browser, the browser reports the SSL certificate is invalid.
Workaround: Use the Internet Explorer or Firefox web browsers.

いや…もうとっくの昔にFirefoxもアウトやでESR版使え(それでもオレオレ証明書の警告出るけど)って書かんと…このドキュメントは今年の1月リリースのものなんだけどこの杜撰さはさすがHPE製品という感じでインフラ屋時代の怒りが再燃してきた、藁人形に五寸釘打っちゃお。

これTLS1.2以降に対応できん理由があるとしたら組込のlighttpd/OpenSSLのバージョンが古いけど人手なのかファームウェアサイズなのか判らんが余裕が足りねえってとこかなぁ、今後も対応は期待薄やね。

まぁHTTP onlyにしたとこでどーせ閉じた自宅ネットワークなので平文パスワード盗聴してくるのは天井と壁のシミに限られるからな、あいつら5Gで俺の脳に直接電話してくるレベルだからHTTPSにしたとこで盗聴くらい余裕だろう、俺のスマホがいまだに4Gだからって脳内に語り掛けてくるのやめてくだち!

ちなみにWebUIはちょいと古めのjQuery UIベースで実装されてる、旧Procurve製品のように今や廃止となり動かすのにも一苦労のJava Appletではないので、これが唯一の設定方法でもこのHTTPS問題を気にしないなら当面は問題無さげ。 認証はパスワード認証のみでクライアント証明書認証や複数要素認証といった方式は無し。セッション管理はCookie必須でログイン/ログアウトでセッションIDは変わるし操作無しで一定時間でタイムアウトして破棄されるので最低限の固定化攻撃対策はしてある感じ。

パスワード認証の初期値は

なのでWebUIからパスワード変更とユーザー名の変更をしておく、最新版のファームウェア(PT.02.11)だと初回ログインでパスワード設定必須になってる。

よって中古購入とか前任者がドキュメント残さずに失踪したなんてチャメシインシデントの場合にユーザー/パスワード不明でログインできないなんて問題が起きうるけど、フロントパネルのresetスイッチをゼムクリップで長押しし工場出荷状態に戻せばいいだけなのでまぁええか。 ファクトリーリセットにより失われた設定内容については精神のステータスを上げて宇宙の過去現在未来が記録されたアカシックレコードにアクセスして復元すればヨシ、簡単ですね額の裏にある松果体に意識を集中して第三の眼を開けばすぐに見えるようになる。

管理用IPアドレスはIPv4のみでIPv6は使えない、初期値は192.168.1.1。うちでは全部無線ルーターにMACアドレス登録してDHCPで管理してるので、Setup Network->Get Connected->Network DetailのProtocol TypeをStatic->DHCPに変更しておく。 どうもApplyボタン押しただけではDHCPクライアント走らないっぽく、設定変更して無線ルーターと繋げたらIPアドレス競合して以下略。Save Configurationした上で更に再起動が必要っぽい。

死活監視はSNMPv2に対応してるので、お好きな監視ツールを使えばよろし。

$ snmpwalk.exe -v2c -c public 192.168.1.2 .1.3.6.1.2.1.1
SNMPv2-MIB::sysDescr.0 = STRING: HPE OfficeConnect Switch 1820 24G J9980A, PT.02.11, Linux 3.6.5-58b5074c, U-Boot 2012.10-00116-g3ab515c (Jul 30 2014 - 10:52:01)
SNMPv2-MIB::sysObjectID.0 = OID: SNMPv2-SMI::enterprises.11.2.3.7.11.168
DISMAN-EVENT-MIB::sysUpTimeInstance = Timeticks: (11301500) 1 day, 7:23:35.00
SNMPv2-MIB::sysContact.0 = STRING:
SNMPv2-MIB::sysName.0 = STRING: hpswitch01
SNMPv2-MIB::sysLocation.0 = STRING:
...

時刻合わせはSNTPが利用できるけどサーバー指定はIPv4かつIPアドレス指定のみ、中継サーバーにもならんので別途ローカルにNTPサーバー建ててそっち向けるんですかね。

ジャンボフレームはHP Microserverに載ってる古いBroadcomのNICがそもそも未対応ちゅー悲しい有様なのでテストせず、スパニングツリープロコルもうちのネットワーク構成では無用なので以下同文。

そんで今回無い金振り絞ってL2スイッチ買った最大の目的であるLACP(IEEE 802.3ad)なのだけど、設定方法が微妙に判りにくいのがアレ。 他のProcurve/Aruba製品だとPort ConfigurationからLACPの設定に入ったと記憶してるのだが、この機種はTrunk Configurationの方から入って

でおこなう。Static ModeでないすなわちDynamic ModeがイコールLACPなのは他にサポートしてるプロトコルが無いからまあそらそうだと納得はできるのだが、LACPのネゴシエーション方法にpaasive/activeの選択が無いってのはどうなんすかねこれactiveのみってことかな。

そんでLoad Balanceモードもぱっとみ判りづらい。

  1. Source MAC, VLAN, Ethertype, Incoming Port
  2. Destination MAC, VLAN, Ethertype, Incoming Port
  3. Source/Destination MAC, VLAN, Ethertype, Incoming Port
  4. Source IP and Source TCP/UDP Port Field
  5. Destination IP and Source TCP/UDP Port Field
  6. Source/Destination IP and Source TCP/UDP Port Field

上からCISCOのsrc-mac, dst-mac, src-dst-mac, src-ip(port), dst-ip(port), src-dst-ip(port)相当って事でええんですかね、ネットワーク屋じゃねえのでわからない俺は雰囲気でスイッチを設定している。 ふつーシスコといったら ロックシティと決まっとる。 とりあえずデフォルトの3.のままにしておく事にしといてそのうちちゃんと真面目に勉強するわ来世で。

そしてセキュリティ機能、1810-24Gの頃から存在したAuto DoSという機能だけどもこいつを有効にすると

というNFSやNTPといったごく普通に使われるサービスが即死するというDoS対策というかお前がDoSそのものだろうという謎仕様は健在なんやなこれ、 被害者 その1。ただし1810はデフォルト有効だったのだけれど1820はデフォルト無効なので、設定㌧でも勝手に有効になることはないので少しはマシになった感。

しっかしこの同一ポート間の通信を遮断することでDoS対策したぜってワイ的には 過去記事でも書いたがLoopback DoS(Land Attack)対策には成功したが患者は死亡したのパターンかなぁと想像してたんだが、この機種だとAuto DoSの詳細設定に

があり、こいつら全てを一括で有効にするのがAuto DoSのチェックボックスとなってる。 そんで ここの投稿によると同一ポート間の通信を全て遮断するのはPrevent TCP/UDP Blat Attackってやつだそうで。

んでBlat攻撃とか知らんかったのでちょいと検索してみたんだが

とLand Attackの一種でそういうのがあるのだね。うんそういう攻撃があるとは理解したがでもなぁL2スイッチが無条件で同一ポート間の通信を勝手にドロップするとか普通思わねえし再起動で勝手に初期化されてしかもデフォルトでこいつがONになるとか知るかよというお話。 つーか他のベンダの製品でもこう無条件にドロップするんだろうか…

そもそもが保守チームに一切の連絡ないまま震災対応!節電!でサーバールームの冷房を切って、サーマルエラーで電源断させた運用チームが戦犯なんだが、なぜ俺が焼き土下座せんとならんかったのかほんと理不尽な話であった。

2021/05/14(Fri)

[オレオレN6] nvi-1.81のPOSIX character classが壊れてる件

かつてnvi-1.81がNにマージされた時に同梱されてるwide string regexがまともに動いてないのをいろいろ直した記憶があるんだが(作業開始がもう 13年前ってマジかよ)、今ようやっとPOSIX character class周りが動いてないのに今更ながら気づいた。

:%s/[[:digit:]]//g

とか叩いてなんで[[:alpha:]]な文字まで消えるんですかね…えーnvi-1.79の頃ってどうだったっけ…

そもそもワイは基本Cygwin上のvim使ってる時間の方が9割なのでな、それに置換もエディタでやらずにsed(1)とかperl(1)使う人なので使わん機能のバグなぞ気づかないのである。 これが時空の歪みが発生する最大の理由であって以下略

なお本家の方はとっとと1.81捨てて nvi2に移行してた記憶がうっすらとあるので、そっちだとちゃんと動いてる可能性はある。 でも今nvi2のregexの下かるく眺めた限りでは1.81とほとんど同じ(つーかワイがNにcommitした変更をnvi2の作者がそのまま持ってったはずなので)なのでダメかもしれない。 まぁわざわざ本家のN入れて試す気にもならないのでどうでもよろし。

そもそもあのwide string regex自体かなり無理矢理な実装なので、POSIX character classもC locale相当の値がハードコードだったりでガリガリとSAN値削られる実装なのだ。 なもんでどーせ将来的にlibcにmultibyte regex(3)入れなきゃならんのだしそれが終わればそいつで置き換えりゃいいと、楽観的展望で作業したからとりあえず常用の範囲で動きゃいいという雑な作業だったからな。

なんでそんな楽観的展望だったかというと根拠が無いわけではなく、GSoCでどっかの学生さんがmultibyte regex実装するぜっていってたからなんだけど、結局どうなったんだっけアレ。 なんか自分では実装は無理でした(笑)とか言いだして、その学生さん選んだmentorの質が問われるエンドだった記憶が…ああいうのばっかで後年NがGSoCから漏れたのまったく驚きは無かったゾ。

どうもN HEADのregex(3)のコードちら見した限りではF由来のマルチバイト対応コードがマージされてるっぽいが、あれ以前見た時にLC_COLLATEがらみでF独自のcollation API直接呼んでてそっ閉じしたんだがそのへんはどうしてんだろう?やっぱりどうでもいいや。

とりあえずwide string regexのベースとなってるHenry Spencer's regexじたいコードが古くてセキュリティ絡みのバグやら仰山あるので、まずはそこの同期してからPOSIX character classのバグ対策やね。

そもそもオレオレN6のlibcの方の実装も大概に古いのでFとOの修正履歴見ながらいろいろコードの更新をかけてるところ、それにしてもFのマルチバイト対応コードはあいかわらずクオリティが酷い…

[オレオレN6] 続・nvi-1.81

どうも根本的にPOSIX character classどころか[]が壊れてるっぽいなぁ。

:%s/[ABC]//g

で「A or B or C」だけでなく「あ」が消えたりとか無茶苦茶な動きをしよる…なんだこれ…

[オレオレN6] nvi2もダメ

とりあえずビルドにCMake要求されてキレそうになったのだけどCMakeのcmath問題を回避してビルド通してnvi2作ってみたがやっぱダメだね。 そもそもwide string regex周りのコードは俺がやっつけでwchar_t 32bit clean化したやつと同じだからそりゃ直ってないよな。

ということで13年間誰もバグに気づかない程度のユーザー数ってことだな、vimはニセモノでnvi最高とかいう声が聞こえてきたりもしたが誰も使ってないのがバレたゾ。きっとみんな本当はVSCodeとかAtom使ってるか未だnvi-m17nでUTF-8?なにそれなのだろう。

[オレオレN6] nvi-1.81/nvi2のcharacter class実装が壊れてる原因だいたい分かった

原因についてregex2.h読んで即座に理解したというかcharacter classを格納するcsetという構造体とそれを扱うマクロがまったくワイド文字対応されてないやん、ひでえなこりゃ。

struct {
	uch *ptr;		/* -> uch [csetsize] */
	uch mask;		/* bit within array */
	uch hash;		/* hash code */
	size_t smultis;
	char *multis;		/* -> char[smulti]  ab\0cd\0ef\0\0 */
} cset;
/* note that CHadd and CHsub are unsafe, and CHIN doesn't yield 0/1 */
#define	CHadd(cs, c)	((cs)->ptr[(uch)(c)] |= (cs)->mask, (cs)->hash += (c))
#define	CHsub(cs, c)	((cs)->ptr[(uch)(c)] &= ~(cs)->mask, (cs)->hash -= (c))
#define	CHIN(cs, c)	((cs)->ptr[(uch)(c)] & (cs)->mask)

はい、uchはunsigned charのhandy typeなので0~255より大きいワイド文字が入ってくると死ぬし、そもそも32bit wchar_tの幅のテーブルなんか持てない。 修正した当時たぶん薄々感づいててめんどくささから目を瞑ったと思われる、さぁガス管か練炭かロープか混ぜるな危険かどれにするか。

まぁ修正方法はリストなりで持てなのだがめんどくせえなぁ、Fのmultibyte regexは対応してるのでそれに合わせて実装するかだな。

typedef struct {
        wint_t          min;
        wint_t          max;
} crange;
typedef struct {
        unsigned char   bmp[NC_MAX / 8];
        wctype_t        *types;
        unsigned int    ntypes;
        wint_t          *wides;
        unsigned int    nwides;
        crange          *ranges;
        unsigned int    nranges;
        int             invert;
        int             icase;
} cset;

ワイド文字が0~255ならbmp、それ以上ならwidesあるいはrangesの配列という実装か。 真面目に実装するにはLC_COLLATEの実装ないと困るのだけどどうすんべ。

あと相変わらずFの連中はwchar_tについての知見が足りてないので

typedef uint32_t sop;	/* strip operator */
typedef uint32_t sopno;
#define	OPRMASK	0xf8000000U
#define	OPDMASK	0x07ffffffU
#define	OPSHIFT	(27U)
#define	OP(n)	((n)&OPRMASK)
#define	OPND(n)	((n)&OPDMASK)
#define	SOP(op, opnd)	((op)|(opnd))
/* operators			   meaning	operand			*/
/*						(back, fwd are offsets)	*/
#define	OEND	(1U<<OPSHIFT)	/* endmarker	-			*/
...

とwchar_tが32bit cleanではなく、26bitより上をフラグに流用してしまっておる。

これなぁwchar_tはあくまでopaque objectなので絶対にこういうコード書いちゃダメなんですよ。 毎回この手のクソコード書いてくるからFは信用ならねえのだよね。 つーかGB18030 localeで困るはずなんだけど、そいや無理矢理4バイトコード圧縮してたから26bitで収まるんかな。

これの正しい修正方法はワイがnvi-1.81のwide string regexでやったように

typedef uint32_t sop;	/* strip operator */
...
struct re_guts {
...
	sop *strip;		/* malloced area for strip */

typedef char sop;	/* strip operator */
...
struct re_guts {
...
	sop *strip;		/* malloced area for strip */
	wchar_t *stripdata;	/* malloced area for stripdata */

と分けるべきなのよね、たいしてメモリ使用量増えるわけでもないしなによりいちいちOP/OPNDマクロで文字とフラグを取り出す処理も無くなって可読性マシになるぞ。

2021/05/16(Sun)

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

ここ数日はnviのwide string regexの修正どうすんべと思案しておって、その関係でN HEADのregex(3)のコードも眺めたのだが、Fの通常運転なドイヒーなクオリティのコードをちゃんと修正した上でNにマージしてる滝川先生への尊敬度がダダ上がりしてるところ。

というのもFのHenry Spencer's regexは Boyer-Moore法による高速化が独自に追加されてるのだけど、size_tを使うべきとこをint使ってるせいでオーバーフローによるDoS成立しそうだなぁとか、何か所かメモリリーク起こしとるなぁと思いながらマージ作業してたのだが、ちゃんとNはそいつら全部潰してあったゾ。 単純にパクってくるのでなくコード読み込んだ上でマージしてるのね。

あとF独自のcollation API使ってるとこも標準関数のstrcoll/wcscoll使って再実装してあったりいい仕事してますね。

なおワイはボイヤー・ムーア法といわれても 大洋ホエールズのレジェンド助っ人泣きのスーパーギタリストおじさんしか思い浮かばんので以下略、というか5月上旬で自力優勝消滅って大洋ホエールズファンのワイでも記憶ねえぞ…

そもそも滝川先生って誰だよ!って話なんだが、NのFounderであるChristos Zoulas氏の事ね、ワイはクリストスとクリステルの違いももはやわかりません。

ただメモリ管理のsize_t overflow対策はcalloc(3)使えば安心みたいなコードが一部残ってるのだよな、OpenBSDのreallocarray(3)と違って0サイズのアロケーションは未定義動作なんだぜあれ。 なのでOではmalloc/calloc/reallocは使わずにすべてreallocarray(3)使うように徹底してるのだけど。

他にもFのコードで大幅にリファクタリングされて差分の大きすぎるパースロジック周りのコード監査は諦めたのかそのままつっこんでて、かつて このcommitで入ったイービルなレギュラーエクスプレッションをイートさせてトゥーディープなリカーションでスタックをイグゾーストしてサービスをデナイアルする攻撃の対策が消し飛んでるっぽいんだが大丈夫ですかねこれ。

コード差分ぱっとみた限りでは((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((以下ryみたいにブラケットを大量に流し込むとアカンぽいけど。 まぁ再現コードが無いので実際に攻撃可能かは知らん。

まぁそもそもFだけでなくOもこの対応はしてないのがな、まぁあっちの人だと同時に入ったスタックでなくヒープイグゾースト対策のひっどいマクロ

#define MEMLIMIT        0x8000000
#define MEMSIZE(p) \
        ((p)->ncsalloc / CHAR_BIT * (p)->g->csetsize + \
        (p)->ncsalloc * sizeof(cset) + \
        (p)->ssize * sizeof(sop))

の部分だけみてこいつら逆にsize_t overflowバグ埋め込んでんじゃねえかとブチ切れて無視した可能性はある。

あとはスタックより先にヒープの方が尽きてそっちの対策が先に発動すりゃ問題は起きないからそこらはしっかり対策してるから気づかない可能性とかかねぇ、わからない俺は雰囲気でregex(3)のコードを弄っている。

[SCM/BTS] BitBucket緊急メンテ

なんかタイトル書いたら南スーダン久美子緊急事態のユニセフ広告が脳内にフラッシュバックしたがどうでもいい。。

前も書いたけど、ここ一か月以上Bitbucketがクソ重い状態が続いてたのでさすがにメンテ対応がはいったもよう。

$ git push

###############################################################################################

   We're performing maintenance.  Please try again in a few moments,
   or follow our progress at https://bitbucket.status.atlassian.com/incidents/5q0zhsqk5dxm

###############################################################################################

ブラウザからチェンジセットの差分が何度リトライしても表示されない状態が続いてたので、さすがに他社に逃げようかと思ってたのだが、改善すればいいね。

しかしGitHub以外ってーとクローンのGitLabくらいしかないので選択肢が無いのだよな、なおSourceForgeは論値。

[オレオレN6] nvi-1.81/nvi2のPOSIX character classが壊れてる原因判明

しょーもないバグを発見してゲラゲラ笑っている。

diff --git a/dist/nvi/regex/regcomp.c b/dist/nvi/regex/regcomp.c
index f5a87157d5..e0a736fb58 100644
--- a/dist/nvi/regex/regcomp.c
+++ b/dist/nvi/regex/regcomp.c
@@ -821,7 +821,7 @@ p_b_cclass(struct parse *p, cset *cs)
 		NEXT();
 	len = p->next - sp;
 	for (cp = cclasses; cp->name != NULL; cp++)
-		if (STRLEN(cp->name) == len && MEMCMP(cp->name, sp, len))
+		if (STRLEN(cp->name) == len && MEMCMP(cp->name, sp, len) == 0)
 			break;
 	if (cp->name == NULL) {
 		/* oops, didn't find it */
@@ -946,7 +946,7 @@ p_b_coll_elem(struct parse *p,
 	}
 	len = p->next - sp;
 	for (cp = cnames; cp->name != NULL; cp++)
-		if (STRLEN(cp->name) == len && MEMCMP(cp->name, sp, len))
+		if (STRLEN(cp->name) == len && MEMCMP(cp->name, sp, len) == 0)
			return(cp->code);	/* known name */
	if (len == 1)
		return(*sp);	/* single character */

そりゃPOSIX character class指定したらなんでもかんでもリストの先頭にあるalnumにマッチしますわ。

この現象、cset構造体がそもそもCHAR_MIN~CHAR_MAXしか受け付けない問題や、あちこちでwchar_tがcharにnallowされてる箇所が残ってる問題では説明つかないからメモリ破壊疑ってずっと関係ないとこ読み進めてて、えらい遠回りしてしまったわ。

さすがに俺の仕込んだバグじゃないからね、nvi-1.81のオリジナルの作者が仕込んだやつなので aymeric@がNにimportした時から存在するバグである。

ちなみにN HEADのnviのソースも見たけどもちろん直って無いので誰もnviなんか使っていないのである。 あ、そもそもlogin:出たら満足して電源切るんだっけ…

あとはcset構造体をワイド文字対応する作業進めるかね…まったくやる気起きねぇというかHenry Spencer's regexの古臭いマクロまみれのコード読んでるとSAN値が削られるのだ。

2021/05/17(Mon)

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

頭が悪いので(このチラシの裏の初期のタイトル、Keep It Simple, i'm Stupidを思い出せ)BM法という字面だけでBL同人誌とPM法の掛け算かなと脳内で解釈されるのだが、このカップリングはアリですかね想定読者層であるシティポップ好きのゆるふわカメラ女子さん(脳内にしか存在しない存在)。

いまのHenry Spencer改造版multibyte regexではBM法はシングルバイトなlocaleとマルチバイトの先頭が自明であるUTF-8 localeでしか有効になってない、まぁそらそうか。 まぁいつも思うけどUTF-8はほんとよくできてるよ、文字集合としてのUnicodeはゴミだけどな!やっぱり文字集合はISO2022かつ符号化手法だけUTF-8な文字コードが人類には必要なのではないか、ちゃんと薬は飲んだか!

後ろに戻ってマルチバイトの途中でマッチしてないかはチェックできないことも無いだろうけど最悪先頭まで戻るし、そもそも可変翼と共に大空を翔る男のロマンであるstateful encodingだと使えんわなこれ。 でもすでに別件で検索開始位置を探すstepbackという関数が増えてて、そこで同じようなことやってるのでja_JP.ISO-2022-JP localeなんかでは動かんコードであるのは確定なのだから別にいいんじゃねという気にもなる。 そもそもja_JP.ISO-2022-JP localeなんて実装すること自体がドダイYS無理なのである。

一点気づいたのがなぜかN HEADでは非UTF-8なmultibyte locaeでも有効になってるのだよな、たとえばEUC-JPやShift_JISなテキストファイルをsed(1)なんかで置換するとぶっ壊れる可能性がある、ご愁傷さまです。 まぁそもそも今時EUC-JPやShift_JISなんか使わん時代だしそもそも自前の正規表現エンジン抱え込んでるLLでテキスト処理するだろうし、そもそもNならlogin:でたら満足して電源落とすから実害はないな。

#ifdef notyet
	/*
	 * It's not generally safe to do a ``char'' substring search on
	 * multibyte character strings, but it's safe for at least
	 * UTF-8 (see RFC 3629).
	 */
	if (MB_CUR_MAX > 1 &&
	    strcmp(_CurrentRuneLocale->__encoding, "UTF-8") != 0)
		return;
#endif

ここFのコード直接rune(3)触りに行ってて、ここの実装がFとNで違うから談話室滝川先生が理解を諦めた感じか、ちゃんと読めばこれだけの差分なんですけどね。

$ diff -upN regcomp.c.orig regcomp.c
--- regcomp.c.orig      2021-03-12 00:00:29.000000000 +0900
+++ regcomp.c   2021-05-17 03:05:41.000000000 +0900
@@ -2021,16 +2021,14 @@ findmust(struct parse *p, struct re_guts
 	if (p->error != 0)
 		return;
 
-#ifdef notyet
 	/*
 	 * It's not generally safe to do a ``char'' substring search on
 	 * multibyte character strings, but it's safe for at least
 	 * UTF-8 (see RFC 3629).
 	 */
 	if (MB_CUR_MAX > 1 &&
-	    strcmp(_CurrentRuneLocale->__encoding, "UTF-8") != 0)
+	    strcmp(_CurrentRuneLocale->rl_codeset, "UTF-8") != 0)
 		return;
-#endif
 
 	/* find the longest OCHAR sequence in strip */
 	newlen = 0;

まぁ例のアレがlocale周り手を入れてるだろうから変わってるかもしれんがそこまで調べる気にはならん。

つーかこんな移植性の無いコードでなくとも現在の文字コードなんてnl_langinfo(CODESET)なりsetlocale(LC_CTYPE, NULL)でクエリできる *1んだけどな。

$ cat >unko.c
#include <langinfo.h>
#include <stdio.h>
#include <locale.h>
int
main(void)
{
	setlocale(LC_ALL, "");
	printf("%s\n", nl_langinfo(CODESET));
	printf("%s\n", setlocale(LC_CTYPE, NULL));
}
^D
$ make unko
cc -O2   -o unko unko.c
$ LANG=ja_JP.UTF-8 ./unko
UTF-8
ja_JP.UTF-8

ここで俄然と関数呼ぶオーバーヘッドガーさんが脳内で戦いを挑んでくるのだが、そういわれましてもここ通るのregexec(3)呼ばれた時ただ一回なんすよね…

んでwide string regexの場合なんだけど、理論上これらの制限は無いはずだけど、いまの実装だとcharjumpテーブルサイズがCHAR_MIN~CHAR_MAXサイズなのでsingle byte localeにしか使えずmultibyte regexより制限きついな、そこの実装を考えないとならない感じかな。 まぁワイの縮退した脳では実装考えるのめんどくさいのでMB_LEN_MAX=1チェックだけで放置するかのう、しょせんnviなので検索や置換に速度が必要な巨大なファイルサイズなんて正規表現エンジンより先にエディタ側が死ぬしな。

*1:まぁ戻り値がポータブルであるかには議論の余地はある

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

前記事でちょっと触れたワイド文字列に対するBM法実装で、リストで持つとかにすると複雑になるし性能アレやなと思ったのだが、そもそも検索文字列に例えばUnicodeの文字全部羅列したものとか指定するとヒープ枯渇DoSが成立しちゃうので、せいぜい256文字とかで十分な気がしてきた。

そもそもエディタで検索する文字列なんてほんの数文字なわけで、検索文字列に含まれる文字種が256を超過したらBM法キャンセルされて速度が低下するって制限仕込んだとこで大した問題じゃねえよな…

これまではL'\0'~L'\xff'の範囲の文字だけのスキップテーブルを作ってたけど、それ以外のワイド文字は検索文字列中に発見した順に配列に放り込んでqsortして、マッチかけるときはbsearchで探すみたいな実装ね。

まぁその分性能は低下するわけだけど、それでもナイーブ法すなわり愚直なマッチングよりは速いんじゃねえかなぁという希望的観測。

ということでクッソ適当に実装してみた、すでにwide string regexにはFによるBM法のコードの部分は マージ済なので、それに対して差分がなるべく小さくなるよう実装した。

diff --git a/dist/nvi/regex/engine.c b/dist/nvi/regex/engine.c
index a6d1d8d6ce..edea43895f 100644
--- a/dist/nvi/regex/engine.c
+++ b/dist/nvi/regex/engine.c
@@ -49,6 +49,7 @@
 #define	at	sat
 #define	match	smat
 #define	nope	snope
+#define	getcharjump	sgetcharjump
 #endif
 #ifdef LNAMES
 #define	matcher	lmatcher
@@ -60,6 +61,7 @@
 #define	at	lat
 #define	match	lmat
 #define	nope	lnope
+#define	getcharjump	lgetcharjump
 #endif
 
 /* another structure passed up and down to avoid zillions of parameters */
@@ -89,6 +91,7 @@ static const RCHAR_T *walk(struct match *, const RCHAR_T *, const RCHAR_T *,
     sopno, sopno, int);
 static states step(struct re_guts *, sopno, sopno, states, int, RCHAR_T,
     states);
+static size_t getcharjump(struct re_guts *, UCHAR_T);
 #define MAX_RECURSION	100
 #define	BOL	(1)
 #define	EOL	(BOL+1)
@@ -159,8 +162,8 @@ matcher(struct re_guts *g, const RCHAR_T *string, size_t nmatch,
 			pp = mustlast;
 			for (dp = start+g->mlen-1; dp < stop;) {
 				/* Fast skip non-matches */
-				while (dp < stop && charjump[(int)*dp])
-					dp += charjump[(int)*dp];
+				while (dp < stop && (cj = getcharjump(g, (UCHAR_T)*dp)))
+					dp += cj;
 
 				if (dp >= stop)
 					break;
@@ -176,7 +179,7 @@ matcher(struct re_guts *g, const RCHAR_T *string, size_t nmatch,
 
 				/* Jump to next possible match */
 				mj = matchjump[pp - mustfirst];
-				cj = charjump[(int)*dp];
+				cj = getcharjump(g, (UCHAR_T)*dp);
 				dp += (cj < mj ? mj : cj);
 				pp = mustlast;
 			}
@@ -941,6 +944,24 @@ step(struct re_guts *g,
 	return(aft);
 }
 
+static size_t
+getcharjump(struct re_guts *g, UCHAR_T c)
+{
+	size_t ret;
+	struct re_bmext key, *bme;
+
+	if (ISCACHED(c)) {
+		ret = g->charjump[(size_t)c];
+	} else {
+		key.c = c;
+		key.n = 0;
+		bme = bsearch(&key, g->charjumpext, g->ncharjumpext,
+		    sizeof(g->charjumpext[0]), re_bmext_cmp);
+		ret = (bme != NULL) ? bme->n : g->mlen;
+	}
+	return ret;
+}
+
 #ifdef REDEBUG
 /*
  - print - print a set of states
@@ -1013,3 +1034,4 @@ pchar(RCHAR_T ch)
 #undef	at
 #undef	match
 #undef	nope
+#undef	getcharjump
diff --git a/dist/nvi/regex/regcomp.c b/dist/nvi/regex/regcomp.c
index e0a736fb58..125896bf88 100644
--- a/dist/nvi/regex/regcomp.c
+++ b/dist/nvi/regex/regcomp.c
@@ -236,10 +236,8 @@ regcomp(regex_t *preg, const RCHAR_T *pattern, int cflags)
 	if (g->mlen > 3) {
 		computejumps(p, g);
 		computematchjumps(p, g);
-		if (g->matchjump == NULL) {
-			free(g->charjump);
+		if (g->matchjump == NULL)
 			g->charjump = NULL;
-		}
 	}
 	g->nplus = pluscount(p, g);
 	g->magic = MAGIC2;
@@ -1697,6 +1695,21 @@ altoffset(sop *scans, RCHAR_T *scand, int offset)
 	return largest+offset;
 }
 
+int
+re_bmext_cmp(const void *a, const void *b)
+{
+	UCHAR_T ac, bc;
+
+	ac = ((const struct re_bmext *)a)->c;
+	bc = ((const struct re_bmext *)b)->c;
+
+	if (ac == bc)
+		return 0;
+	else if (ac < bc)
+		return -1;
+	return 1;
+}
+
 /*
  - computejumps - compute char jumps for BM scan
  *
@@ -1710,33 +1723,51 @@ altoffset(sop *scans, RCHAR_T *scand, int offset)
 static void
 computejumps(struct parse *p, struct re_guts *g)
 {
-	int ch;
-	size_t mindex;
+	size_t i, j, n;
+	UCHAR_T c;
+	struct re_bmext *bme;
 
 	/* 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;
+	for (i = 0; i < __arraycount(g->charjumpbuf); ++i)
+		g->charjumpbuf[i] = 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;
+	for (i = 0; i < g->mlen; ++i) {
+		c = (UCHAR_T)g->must[i];
+		n = g->mlen - i - 1;
+		if (ISCACHED(c)) {
+			g->charjumpbuf[(size_t)c] = n;
+			continue;
+		}
+		bme = NULL;
+		for (j = 0; j < g->ncharjumpext; ++j) {
+			if (g->charjumpext[j].c == c) {
+				bme = &g->charjumpext[j];
+				break;
+			}
+		}
+		if (bme == NULL) {
+			if (g->ncharjumpext >= __arraycount(g->charjumpext))
+				return;
+			bme = &g->charjumpext[g->ncharjumpext++];
+			bme->c = c;
+		}
+		bme->n = n;
+	}
+	qsort(g->charjumpext, g->ncharjumpext,
+	    sizeof(g->charjumpext[0]), re_bmext_cmp);
+
+	g->charjump = g->charjumpbuf;
 }
 
 /*
diff --git a/dist/nvi/regex/regex2.h b/dist/nvi/regex/regex2.h
index 91b0ec682a..c1d1d27243 100644
--- a/dist/nvi/regex/regex2.h
+++ b/dist/nvi/regex/regex2.h
@@ -119,6 +119,16 @@ CHIN(const cset *cs, char c)
 	return (cs->ptr[(uch)c] & cs->mask) != 0;
 }
 
+#define CACHE_SIZE	(UCHAR_MAX+1)
+#define ISCACHED(c)	(((c) & ~UCHAR_MAX) == 0)
+
+struct re_bmext {
+	UCHAR_T c;
+	size_t n;
+};
+
+int re_bmext_cmp(const void *a, const void *b);
+
 /*
  * main compiled-expression structure
  */
@@ -144,6 +154,9 @@ struct re_guts {
 	RCHAR_T *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 charjumpbuf[CACHE_SIZE];
+	struct re_bmext charjumpext[CACHE_SIZE];
+	size_t ncharjumpext;
 	size_t *matchjump;	/* Boyer-Moore match jump table */
 	size_t mlen;		/* length of must */
 	size_t nsub;		/* copy of re_nsub */
diff --git a/dist/nvi/regex/regfree.c b/dist/nvi/regex/regfree.c
index 0c2d122816..7e16b653f8 100644
--- a/dist/nvi/regex/regfree.c
+++ b/dist/nvi/regex/regfree.c
@@ -33,6 +33,7 @@
  */
 
 #include <sys/types.h>
+#include <limits.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <regex.h>

つーかFの実装が酷いんだよなぁ、アルゴリズムだけ汎用的なコード書けるだろうに、引数にstruct parserとかstruct re_gutsとか要求するクソI/Fなので使い回しの効かないコードになってる、どうせだから切り出して汎用的なコードにしますかね。

これでどのくらい性能劣化するかなんだが、測定するために別途ライブラリとして切り出してさらにテストケース書くのがめんどくさいので当面は放置すると思われる、もう全部来世に先送りしていいですか?

というかstrstr(3)とかwcswcs(3)ってナイーブ法で実装されてるけど、BM法な実装ってありなんだっけ?C++17だとstd::boyer_moore_searcherなんて生えたそうだけど。

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);

2021/05/19(Wed)

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

昨日のregex(3)のBM法をlibcのbm(3)で置き換える差分、こいつ適用してもtest/lib/libc/regex以下のテストは完走したのでとりあえず作業マシンに入れて常用してみたのだが、GNU configureが途中でコケるという現象が起きてるな。

config.status: error: Something went wrong bootstrapping makefile fragments
    for automatic dependency tracking.  If GNU make was not used, consider
    re-running the configure script with MAKE="gmake" (or whatever is
    necessary).  You can also try re-running configure with the
    '--disable-dependency-tracking' option to at least be able to build
    the package (albeit without support for automatic dependency tracking).
See `config.log' for more details

ということでロールバック、なんか使い方間違ってるのかそもそも動かないコードなのか…うーんめんどくせえやっぱり別途用意するかのう。

それとbm_comp(3)に渡す第3引数の頻度データの話、よく考えると言語毎に統計とらんでも今やUnicode絵文字によって人類がどんどん退化しているので頻度上位99文字全てが絵文字じゃねえのかという気がしてきた。

なので顔文字メインに99個適当に選べばいいのでは…という結論に至った、g17nは絵文字によって達成されもはやi18n/l10nなんてのは絵文字を使わない新人類と意思の疎通ができない旧人類すなわち猿人のためのレガシーコストなんですな。

昔Unicode2.0でハングル文字大移動なんて事件があったけど、たぶん23世紀末までに絵文字をすべて基本面に移動するって提案がされると予言しておくぜ。 同時にキーボードも全部絵文字になるからQWERTYの由来について安岡先生がツッコミを入れる必要も無くなる平和な世界が訪れますね。

一方ではUIのアイコンがフラットデザインの大流行で「三」がリストメニューの意味だったりとピクトグラムであるべきものが表意文字並みの難解さに変異してるのだが、古代の人類も象形文字みて「最近の若いデザイナーはこんな判りにくいデザインにして莫迦じゃねーのか」とか思ってたんだろうなぁ。

たぶん佐〇可士和みたいなネアンデルタール人がオシャレさ優先でデザインした壁画絵に苦情が殺到し、上から羊皮紙とかパピルスとか粘土板で注釈貼って運用で対処とかやってたと思う。

2021/05/20(Thu)

[わからない] もう何もわからない

そもそもITってのは反復業務には強いけど、予期せぬ緊急事態への即応性なんぞ開発期間がボトルネックになるから皆無って認識を皆が持ってほしいよな、FAXと人力がダサいと思ってる人こそIT音痴だってそろそろ気づこう。 それともデジタル庁から赤紙でスーパープログラマ動員してデスマ従事させたあと戦時徴用船みたいに補償金ですただし特別税100%な!ってやってみる?

すぐに沸いてくるIT後進国!日本にGAFAM *1は生まれない!とぶちあげて気持ちよくなりたがる手合いは無視でいいよ、そういうのに限って毎年のように億人単位の個人情報を漏洩させるFacebookの「完璧目指すよりまず終わらせろ」を名言とか担ぎ上げるダブスタ野郎だし *2

プログラマの美徳とされるものに「手動でやるより何倍もの時間がかかってもプログラムを書いて処理する」ってのがあるけど、裏を返せば「即応性ならいまだ人力の方が勝る」ともいえるんだよな。 いまのIT神話の火付け役の一角であるAmazonだってMechanical Turkみたいなスーパー低お賃金人海戦術部隊なんぞ囲ってるわけでな。

あとCOCOAのバグ放置問題、AppleとGoogleがAPIの利用を一国一組織って制限つけたせいで代替アプリが存在しない状態になってしまった事はもっと失敗の原因として挙げられるべきよ、その分開発者も減るわけで情報共有ができなくなるからね。 もちろん悪意のある偽アプリが蔓延することで社会的混乱を防ぐ意図はわかるんだけど、じゃあそもそもストア審査って何のためにあるんでしたっけって話でな。 ああ審査なんてザルもいいとこでその実は高っかい高っかいショバ代徴収するための名目上の理由したっけウフフ。

さてどうでもいい話はおいといて、滝沢先生が修正したregex(3)のBM法のコード、integer overflowの対策はしてあるなと感心してたが、size_t overflowの方の対策は見過ごしてて草。 まぁ検索文字列長 + 検索対象文字列長がsize_tを超えるってまずありえないのでワイの方がお薬必要なだけな気がしないでもない、途中でヒープ枯渇するなりmmap(2)の制限にひっかかるからな…

あとmatchjump(suffixのmismatchを求めるテーブル)の生成がちょっとややこしいコードなんだけど(pmatchesなんていう一時テーブル用意したり)、普通もっとシンプルなコードだよねぇ。 これでテーブル生成高速化できるとかあるのかな、うーむ読み解かないとならん…

それとBM法を非UTF-8なmultibyte localeでも有効にするため、前に戻ってmultibyteの途中にマッチしてないかを探すAPIをi18n encoding moduleに追加べきなのか相変わらず考えがまとまらない。 問題はISO-2022-JPとかだけどあれもlead byteを探すでなくなくエスケープシーケンスの0x1bを探せば移動量の問題はあるけど可能ではあるし。 でもそもそも検索パターン文字列が完全に変換可能なmultibyteであることって規定あるんだっけ?それこそmultibyteの途中からはじまる検索パターンを指定した場合マッチしなくなるよな、でもregcomp(3)失敗するからいいのか。 パラノイア過ぎる気もするのだがわからないもうなにもわからない日々なのだ。

関係ないけどその過程で思い出したのがnvi-1.81をja_JP.ISO-2022-JP localeで動くようにするのに、どのようにしてモード切替のESCとエスケープシーケンス開始の0x1bを区別するのかという難問。 ちなみにnvi-m17nでは0x1bが入力されてから一定時間経過したらモード切替という苦肉の策だったような記憶がある…

あとnvi-1.81のset fileencodingのバックエンドであるconv.cでのiconv(3)の使い方がアレな件も思い出してしまった、当時そこまでやる時間なかったんだよなぁ。

そもそも人類にiconv(3)は難し過ぎるので、VisualC/C++のfopen("ccs=encoding")みたいな拡張で隠すべきと思ってるんだけどね、それをいったらどっかのドイツ人に鼻で笑われた記憶があるけどまあ一生iconv(3)とダンスしててください。 はっきりいってこの世に正しいiconv(3)の使い方をしてるコードって片手で足りるんじゃねえの感あるゾ。

移植性考えないのならfunopen2(3)とかfopencookie(3)でfopen("ccs=encoding")的なもの実装しちまうのだけど、BSDとglibc以外を考えるとアレ。でも今fmemopen(3)とかopen_memstream(3)のバックエンドとしてこの手の機能必要になってるはずなのだがSolarisあたりどうしてるんだろうな。 もはやOracleのログインパスワードなんか覚えてないのでSolaris11落としてくる気にもならんのだが。

また別の話だけど、先日opensslをgit subtree化する作業をやった後、build releaseは完走するのにbuild release -uでobjを残した状態で再ビルドするとbinutilsのgasのバグ踏んでるのかopensslのasmコードのビルドがコケるので困る。 とりあえずbinutilsを最新にした方が良さそうだ、またやらんとならん作業が増えたやはりワンオペは厳しいねその分何の責任も無いから気楽でいいけど。

*1:G-MAFIAの語呂合わせに巻き込まれるIBMっていま何が本業なのだろう…
*2:まぁTRON陰謀論とか信じるよりはまだマシか…

2021/05/21(Fri)

[オレオレN6] もう何も以下略

libcのbm(3)呼んでる部分だけ自分で書いたBM法のコードに置き換えたらGNU configureもちゃんと完走するので、戦犯Keith Bosticじゃねえの疑惑が高まってきた、以下差分。

diff --git a/lib/libc/include/namespace.h b/lib/libc/include/namespace.h
index 138ec66b8c3..8a53c765079 100644
--- a/lib/libc/include/namespace.h
+++ b/lib/libc/include/namespace.h
@@ -513,6 +513,9 @@
 #define regerror		_regerror
 #define regexec			_regexec
 #define regfree			_regfree
+#define re_bm_comp		_re_bm_comp
+#define re_bm_exec		_re_bm_exec
+#define re_bm_free		_re_bm_free
 #define registerrpc		_registerrpc
 #define res_init		_res_init
 #define res_mkquery		_res_mkquery
diff --git a/lib/libc/regex/Makefile.inc b/lib/libc/regex/Makefile.inc
index bf087c110b3..14fad6bcf6e 100644
--- a/lib/libc/regex/Makefile.inc
+++ b/lib/libc/regex/Makefile.inc
@@ -3,7 +3,7 @@
 
 CPPFLAGS+=-DPOSIX_MISTAKE
 
-SRCS+=	regcomp.c regerror.c regexec.c regfree.c
+SRCS+=	regcomp.c regerror.c regexec.c regfree.c regbm.c
 
 MAN+=	regex.3 re_format.7
 
diff --git a/lib/libc/regex/engine.c b/lib/libc/regex/engine.c
index 06d9c251eeb..9485ab3b03f 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,12 @@ 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->bmpat != NULL)
+			dp = re_bm_exec(g->bmpat, start, (size_t)(stop - start));
+		else
+			dp = memmem(start, (size_t)(stop - start), g->must, g->mlen);
+		if (dp == NULL)
+			return REG_NOMATCH;
 	}
 
 	/* match struct setup */
diff --git a/lib/libc/regex/regbm.c b/lib/libc/regex/regbm.c
new file mode 100644
index 00000000000..8b4f455a818
--- /dev/null
+++ b/lib/libc/regex/regbm.c
@@ -0,0 +1,111 @@
+/*-
+ * Copyright (c)2021 Takehiko NOZAKI,
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include "namespace.h"
+#include <sys/param.h>
+#include <assert.h>
+#include <limits.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <wchar.h>
+#include "regbm.h"
+
+struct re_bmpat {
+	const char *pat;
+	size_t patlen;
+	size_t cjump[UCHAR_MAX+1];
+	size_t mjump[];
+};
+
+#ifndef MAX
+#define MAX(a, b)	(((a) > (b)) ? (a) : (b))
+#endif
+
+re_bmpat_t
+re_bm_comp(const char *pat, size_t patlen)
+{
+	re_bmpat_t b;
+	size_t lastp, i, n, suffix;
+
+	lastp = patlen - 1;
+	if (patlen > SIZE_MAX / sizeof(b->mjump[0]) - sizeof(*b) ||
+	    (b = malloc(sizeof(*b) + patlen * sizeof(b->mjump[0]))) == NULL)
+		return NULL;
+	for (i = 0; i < __arraycount(b->cjump); ++i)
+		b->cjump[i] = patlen;
+	for (i = 0; i < patlen; ++i)
+		b->cjump[(unsigned char)pat[i]] = lastp - i;
+	for (i = patlen; i-- > 0; /**/) {
+		n = i + 1;
+		b->mjump[i] = (!memcmp(pat, &pat[n], patlen - n))
+		    ? lastp + n - i : lastp * 2 - i;
+	}
+	for (i = 0; i < lastp; ++i) {
+		for (suffix = 0; suffix < i; ++suffix) {
+			n = lastp - suffix;
+			if (pat[i - suffix] != pat[n]) {
+				b->mjump[n] = lastp + suffix - i;
+				break;
+			}
+		}
+	}
+	b->pat = pat;
+	b->patlen = patlen;
+	return b;
+}
+
+const char *
+re_bm_exec(re_bmpat_t b, const char *s, size_t slen)
+{
+	size_t lastp, si, pi, jump;
+
+	if (slen >= b->patlen) {
+		lastp = b->patlen - 1;
+		for (si = lastp; /**/; si += jump) {
+			while ((jump = b->cjump[(unsigned char)s[si]]) > 0) {
+				if (si > slen - jump)
+					return NULL;
+				si += jump;
+			}
+			for (pi = lastp; s[--si] == b->pat[--pi]; /**/) {
+				if (pi == 0)
+					return s + si;
+			}
+			jump = MAX(b->cjump[(unsigned char)s[si]], b->mjump[pi]);
+			if (si > slen - jump)
+				break;
+		}
+	}
+	return NULL;
+}
+
+void
+re_bm_free(re_bmpat_t b)
+{
+	free(b);
+}
diff --git a/lib/libc/regex/regbm.h b/lib/libc/regex/regbm.h
new file mode 100644
index 00000000000..b9260c9ad82
--- /dev/null
+++ b/lib/libc/regex/regbm.h
@@ -0,0 +1,36 @@
+/*-
+ * Copyright (c)2021 Takehiko NOZAKI,
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#ifndef REGBM_H_
+#define REGBM_H_
+
+typedef struct re_bmpat *re_bmpat_t;
+
+re_bmpat_t re_bm_comp(const char *, size_t);
+const char *re_bm_exec(re_bmpat_t, const char *, size_t);
+void re_bm_free(re_bmpat_t);
+
+#endif
diff --git a/lib/libc/regex/regcomp.c b/lib/libc/regex/regcomp.c
index 8b2101db2a1..ebc4a041550 100644
--- a/lib/libc/regex/regcomp.c
+++ b/lib/libc/regex/regcomp.c
@@ -50,6 +50,7 @@ __weak_alias(regcomp,_regcomp)
 #endif
 
 #include "utils.h"
+#include "regbm.h"
 #include "regex2.h"
 
 #include "cclass.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->bmpat = 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->bmpat = re_bm_comp(g->must, g->mlen);
 	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 3d2fb692407..88709de210d 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 */
+	re_bmpat_t bmpat;
 	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 9aa0a14bf5f..5cac2663025 100644
--- a/lib/libc/regex/regexec.c
+++ b/lib/libc/regex/regexec.c
@@ -57,6 +57,7 @@ __weak_alias(regexec,_regexec)
 #endif
 
 #include "utils.h"
+#include "regbm.h"
 #include "regex2.h"
 
 /* macros for manipulating states, small version */
diff --git a/lib/libc/regex/regfree.c b/lib/libc/regex/regfree.c
index 4e9ef361786..2b1c8978fa6 100644
--- a/lib/libc/regex/regfree.c
+++ b/lib/libc/regex/regfree.c
@@ -47,6 +47,7 @@ __weak_alias(regfree,_regfree)
 #endif
 
 #include "utils.h"
+#include "regbm.h"
 #include "regex2.h"
 
 /*
@@ -72,6 +73,8 @@ regfree(regex_t *preg)
 	free(g->strip);
 	free(g->sets);
 	free(g->setbits);
+	if (g->bmpat != NULL)
+		re_bm_free(g->bmpat);
 	free(g->must);
 	free(g);
 }

できる限りはbm(3)を使う方向性でいきたいのでbm(3)のバグ調査せんとならない、もう何もわからない…

[WWW] IE11終了

命日決まってJava Appletが動くブラウザが無くなるわけだがどうしたもんかね(古いネットワーク機器なんかで困る)。 まぁJREも脆弱性のある古いバージョンじゃないとJava Plugin自体含まれてないわけで、IE使い続けたところで何の問題も無いという話はある。

誰かAppletタグ横取りしてJavaバイトコードをJavaScriptに変換して実行するブラウザ拡張作ってくだち! Shockwave Flashの場合はその手のプロジェクトがポコポコ生まれては死んでるというのにどうしてこう人気ないかね。

興味本位でJavaScriptで書かれたJava Bytecode to JavaScript Transpilerなんて酔狂なものあるか探したが、エンゼルスの中継ぎ投手並みに見つからんな。 まぁJavaで書かれたものなら Java bytecode to JavaScript/WebAssembly Transpilerとかいくらでも存在するのだけど、ネイティブだしbytecode弄る系のライブラリ豊富だから作りやすいわけで、それをわざわざJavaScriptでなんて考えるのはそれこそ異常者なんやな。

これの作者のページに、Javaで書かれたソースをJavaScriptに変換する GWT(Google Web Toolkit)という昔あった(今もあるってば)フレームワークへの言及があってちょっと懐かしくなったゾ。

あれなぁGUIウィジェットクラスがAWT/Swingではなく独自のものだし、既存のApplet/Swingアプリケーションを書き直さずに変換するって事ができなかったので流行らなかったな。 要するに時代遅れのJava屋(新時代のCOBOLerなんやな)を再教育することなくHTML5アプリケーション書かせなきゃならないという亡者のあえぐ辺獄にしか需要のないシロモノだったんだな *1

それと変換にかかる時間が遅すぎてな、どれくらい遅いかというと工数の見積もりを大幅に見誤って納期延ばすために焼き土下座する羽目になったくらいで。 まぁあれは開発環境が拷問級低スペックのノートPC(Vista Readyだぞ)だったせいも大きい、予算の権限がなくただ上流から貸与されたお古のマシンしか無い最下層SIerの悲哀なんやな、ほんと理不尽。

ワイは素のGWTはいろいろとクソ過ぎたので、SmartClientというAjaxフレームワークをGWTでラップした SmartGWTというものを選んだのだが、そのSmartGWTもEclipse Pluginがクッソ不安定でな、結局サポート打ち切りでGUIビルダーとして使えるものが無くなってしまったのが痛かった。

こいつにはとてもよく出来た 商用のGUIビルダーがちゃんと存在するのだけど、前述のとおり予算の権限なぞ一切無い奴隷だったので買ってもらえず、仕方なしに最新版では動かなくなった古いEclipse Pluginにバージョン誤魔化すパッチ当てて開発してた思い出。

もはやモバイルアプリの時代でAjax自体がオワコンな気もするし最近の流行とか追ってないから(育毛剤っぽい名のReactとか鹿島っぽいAngularJSとか?)比較対象が古くなるけど、AjaxフレームワークとしてもExtJSやjQuery UIなんかよりよっぽどSmartClientはよくできてるんだよな、なんでこんなに知名度が無いのだろうな。

まぁ「よくできてる」の基準がワイの考えるもっとも優れたGUIアプリケーション開発環境がDelphi5というあたりで若い人と致命的な感覚のズレがあるかもしれん、いやですね老いるのはなるべくはやくポックリ逝きたいですね。

あ、SmartClientはモバイル対応と国際化(特にBiDiの絡むRTLな言語圏)で遅れてる感はあるな、今の時代致命的ですかねこれ…

いろいろ調べるとGWTと同じコンセプトのやつは TeamVMとか JSweetとかあるけど、TypeScriptみたいになんでもっと流行らないんだろうな、ああ「Javaだから」か…経歴書にJavaなんてあったらろくでもない現場ばっかり回されるもんな…

そういえばTcl/Tk版のAppletであるTclet Pluginも動かなくなるわけだけど、あれまったく流行りませんでしたね記憶ではNASAが業務で使ってるとかなんとかいってたはずだがまだ使ってるのかな。

あと一度仕事で使わされたことのある国内企業で地味に使われてるBiz/BrowserってRIAフレームワークも終わるなと思ったら、Biz/Browser DTというJava WebStart的なものが再発明されてたのでまだ死なない模様。 あれも変な言語だったなぁ、だいぶ昔の話だけど言語パーサーにバグがようけあって構文エラーでも動き続けてデバッグに苦労した記憶。

*1:そもそもJavaすら怪しいのだから何で書かせても結果は同じという話もあるが、スキル高くないのに型安全でない言語書かせるのはガソリン被るようなものでな、主に修正する俺が。

2021/05/22(Sat)

[オレオレN6] bm(3)にオーバーラン系のバグがあったもよう

やっぱbm(3)のバグじゃねーか、おのれKeith!

つーかN本家はとっくの7年前に直ってたことに問題個所特定した後で気づいたよクソァ!当時まだサポート中のN6 STABLEへのpullupサボってたもよう、仮にもlibc関数のオーバーランだし使ってるアプリ無くてもそこはちゃんとしようや。

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)];
 		}

つーかこの実装ってただのBM法ではないのはすぐわかったけど改良版のSunday法ってやつか、ペーパーは こちら。 ここのサンプルコードほぼそのままでバグもここ由来、KeithすまんかったおのれSunday!

というかKeithは気づいてたのか修正試みて失敗してる感じやな、オリジナルだと

	s = base+pat.patlen-1;
	e = base+n;

と検索対象文字列の最後までufast skip loopを試みるけど

        s = base + (pat->patlen - 1);

        /* fast loop up to n - 3 * patlen */
        e = base + n - 3 * pat->patlen;

と検索文字列の長さ3倍減じることでガードしたつもりだったのかなと、d0の各要素はpat->patlen-1超えない前提で。 なんとKeith Bostic級のグルでもわからない俺は雰囲気で実装してるなんてあるんだなぁ。

性能については素のBM法に比べてたった1文字移動量が多くなることで速くなるそうで、チリも積もれば何とやら。

これで動くようになったのでとりあえず 前の差分をcommitしておいたが、国際化絡み考えると性能落ちても素のBM法の方がいい気がするし悩ましいね。

まぁnviのワイド文字版regexのcharacter classバグの方が優先度高いのでそっちやるか…

[プログラミング] カレンダーの国際化

kbkさんとこ、Nのcal(1)だと-R(Reform)オプションでイギリス以外でも表示できますな。

そもそもcal(1)の国際化にはPOSIX localeは完全に役立たずなのよね、まず第一にグレゴリオ暦以外扱えないという話は 以前書いたとおり。

ということでその辺のデータにはcal(1)が自前で持ってる、以下はNのcal(1)のソース。

static struct reform {
	const char *country;
	int ambiguity, year, month, date;
	long first_missing_day;
	int missing_days;
	/*
	 * That's 2 for standard/julian display, 4 for months possibly
	 * affected by the Gregorian shift, and MAXDAYS + 1 for the
	 * days that get displayed, plus a crib slot.
	 */
} *reform, reforms[] = {
	{ "DEFAULT",		0, 1752,  9,  3, 0, 0 },
	{ "Italy",		1, 1582, 10,  5, 0, 0 },
	{ "Spain",		1, 1582, 10,  5, 0, 0 },
	{ "Portugal",		1, 1582, 10,  5, 0, 0 },
	{ "Poland",		1, 1582, 10,  5, 0, 0 },
	{ "France",		2, 1582, 12, 10, 0, 0 },
	{ "Luxembourg",		2, 1582, 12, 22, 0, 0 },
	{ "Netherlands",	2, 1582, 12, 22, 0, 0 },
	{ "Bavaria",		0, 1583, 10,  6, 0, 0 },
	{ "Austria",		2, 1584,  1,  7, 0, 0 },
	{ "Switzerland",	2, 1584,  1, 12, 0, 0 },
	{ "Hungary",		0, 1587, 10, 22, 0, 0 },
	{ "Germany",		0, 1700,  2, 19, 0, 0 },
	{ "Norway",		0, 1700,  2, 19, 0, 0 },
	{ "Denmark",		0, 1700,  2, 19, 0, 0 },
	{ "Great Britain",	0, 1752,  9,  3, 0, 0 },
	{ "England",		0, 1752,  9,  3, 0, 0 },
	{ "America",		0, 1752,  9,  3, 0, 0 },
	{ "Sweden",		0, 1753,  2, 18, 0, 0 },
	{ "Finland",		0, 1753,  2, 18, 0, 0 },
	{ "Japan",		0, 1872, 12, 20, 0, 0 },
	{ "China",		0, 1911, 11,  7, 0, 0 },
	{ "Bulgaria",		0, 1916,  4,  1, 0, 0 },
	{ "U.S.S.R.",		0, 1918,  2,  1, 0, 0 },
	{ "Serbia",		0, 1919,  1, 19, 0, 0 },
	{ "Romania",		0, 1919,  1, 19, 0, 0 },
	{ "Greece",		0, 1924,  3, 10, 0, 0 },
	{ "Turkey",		0, 1925, 12, 19, 0, 0 },
	{ "Egypt",		0, 1928,  9, 18, 0, 0 },
	{ NULL,			0,    0,  0,  0, 0, 0 },
};

ここで注目すべきは"Japan"の項が1872/12/20になってることやね。

$ cal -R Japan 12 1872
   December 1872
 S  M Tu  W Th  F  S
                1  2
 3  4  5  6  7  8  9
10 11 12 13 14 15 16
17 18 19


ハイクソー、日本人の感覚では明治5年12月3~19日なんて存在しないんですがこれはNのcal(1)の仕様やね。 そもそも日本はユリウス暦を採用してた事は無くグレゴリオ暦の前は寛政暦だったのだけど、cal(1)はユリウス暦と決めつけてるわけ、どこの異世界カレンダーかよ。

とはいえ日本だと150年前ものカレンダーを表示する必要性ほぼ無いのでイラっとくることも少ないのだけど、つい2016年までヒジュラ歴を採用してたサウジアラビアなんかでは混乱するんじゃねぇかな。 つーかすでに存在するエントリでもトルコとエジプトは明らかに問題なはずよね、それこそイスラム的にユリウス暦すなわち十字軍野郎の暦を使ってたことにされるとか怒られない?

という余計な心配してしまうのだが、そもそもイスラムのヒジュラ暦って太陰暦だからどんどん季節とズレてくので、ルーミー暦(キュロス紀元の春分の日を起点としたユリウス暦)も併用してたのでまぁいいか…

他にもツッコミどころ多くて独立宣言の1776年以前から存在するAmericaとか、この2021年にU.S.S.Rがまだ存在してたりな(ソ連関連のネタはもうひとつあるがまた後で)、よろしいシベリア送りだ。

話を戻して、他にも国際化が必要なものに言語地域によって週の開始が日曜だったり月曜だったりがあるのだけどこの情報もLC_TIMEは持ってない。 いちおう TR14652では拡張してこのへんの情報も持とうという方向性だったのだけど、廃案になってしまったのでな。

こいつらはglibc2には実装されてるので(というかこっちが元だし)locale(1)の-kオプションか、C言語からならnl_langinfo(3)に

を渡すと取得できる、もちろん移植性は皆無なので使わない方がいいけど。

そんでさっきのソ連の話につながるのだが、そもそもPOSIX localeだと非週7日制の暦たとえば

が扱えないのよね、神は納期7日で世界作って最後の1日でやるべきテストをサボったから世の中争いが絶えないのでどんどん変えていこう。

いくら週7日制というものが月の満ち欠けの周期を4で割った近似値で人類のDNAに刷り込まれたものとはいえ、プラゴミの収集日が7日に一回って少ねえよ横浜市!よって週5日制が妥当だと思います、よし革命だ。

これについてもglibc2の開発者の連中はパラノイア極めてるのか

なんてパラメーターが増えてたりする(こちらはlocaleコマンドからは不可視)、莫迦じゃねえの(褒め)。 これきっとオー〇ン〇〇エ〇ィ財団からの資金援助で実装され、〇ラー革命が全世界で成功した後は労働者を奴隷とすべく週365~6日制(週休2日、ホワイトだなあぁ)を施行するための準備と思われる、おのれ〇ョージ・ソ〇ス!(陰謀論) *1

しかしこの_NL_TIME_WEEK_NDAYSだけじゃDAY_7/ABDAY_7より大きい曜日扱えないわけで、まったく意味ないのだ、やっぱりglibc2莫迦じゃねえの(dissり)。

*1:まったくどうでもいいけど陰謀論者ができあがるまでを知りたければP.K.ディックの「戦争が終り、世界の終りが始まった」を読むとよい、ちょうどハヤカワで「ジャック・イジドアの告白」に改題して再刊されたし。 ディック本人がなぜ敵国人差別とオカルトに傾倒したのかその世情と自身の育った環境を自虐的に書き残している、いまの世に読み返すとおもしろいよ。 それとソヴィエト革命暦の採用に他国でもっとも熱心だったのはアメリカだったって話、昨今の騒動で隠れ共産主義者が多いのが可視化された後だと興味深いよね…

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であれば[:kanji:]とか[:hira:][:kana:]なんてのが許される、*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が正常に動くようになる…なんじゃこりゃ。

2021/05/24(Mon)

[オレオレN6] 続・bm(3)のバグのお話

Sunday法についてもうちょっと理解を深めていくことにしたいと思う、何の意味があるかは知らんが。

@Sunday法の高速化の隠し味である4.1.5 ufast loopを読み解く

前提条件として

  • 検索対象文字列のケツに
  • 検索パターン文字列と同じ長さのガード領域(いわゆる番兵)を用意する
  • そこを検索パターン文字列の末尾1文字で埋める*1

ことが可能であることが必須、よってstrstr(3)やregex(3)的なconst char *を引数に取るI/F設計ではこの番兵領域を用意することができないという問題がある。

この4.1.5 ufast loopで行っているのは「不一致文字だったらその文字からテーブルを引いて移動量を求め現在位置を進める」という処理。

通常なら

1	while (s < e) {
2		while ((k = d0[*s]) != 0) {
3			if (s >= e - k)
4				return NULL;
5			s += k;
6		}
7		...
8	}

ちゅー感じで

  • 2行目 … 移動距離 k が0ではないこと、すなわち検索パターン文字列の末尾と不一致のチェック
  • 3行目 … s が k 移動した場合に e を超えないこと、すなわちOOB(Out Of Bounds)してないことのチェック

というコードを書くところだ。

ところがufast loopの実装ではループをアンロールして高速化を図っている。

1	while (s < e) {
2		k = d0[*s];             /* ufast skip loop */
3		while (k) {
4			k = d0[*(s += k)];
5			k = d0[*(s += k)];
6			k = d0[*(s += k)];
7		}
8		if (s >= e)
9			break;
10		...
11	}

4~6行目で都合3回OOBチェック無しにsを移動させてますな、この僅かな差が性能向上に繋がってるってことね。 なぜ3回なのか、それはペーパーでは1~6回アンロールした結果を比較してバランス的に3回を選んだとあるので、別に増やしても減らしてもよいそうだ。

なおワイは頭が悪いので最初は

  • 4~5行目でk == 0でループ脱出条件を満たしても
  • 6行目がk != 0だったらループ脱出できない

よって場合によっては無限ループにならねえか?と思ってしまったのだけど、ちょっと考えると問題ないことが判る。

たとえば4行目で0が返されたら5行目でのsの移動距離はゼロなので4行目と同じ結果が返る、よって6行目も以下同文、つまり3回のうち1回でも条件満たせば安全にループ抜けられることが保証されているのだ。

だからこそ3回ループ展開してもガード領域の長さは3回分でなく1回分で十分なわけ、1回でもガード領域を踏んだらk == 0が保証されるからそれ以上後ろにはアクセスしないのでな。

ここまで理解すればこのテクニックはガード領域がないと成立しないということがわかるよね…

しかしKeith BosticちゅーGuruレベルの人でも、メインループの終了条件であるeすなわちbase(検索対象文字列)のケツ

	s = base+pat.patlen-1;
	e = base+n;
	memset(e, pat[patlen–1], patlen);
	while (s < e) {
		while (k) {
 			k = d0[*(s += k)];
			...
 		}
	}

↑を↓に変更すれば動くだろくらいのノリで論文斜め読みで実装するんだなぁと思いましたまる。

	s = base + (pat->patlen - 1);
	e = base + n - 3 * pat->patlen;
	while (s < e) {
		while (k) {
 			k = d0[*(s += k)];
			...
 		}
	}

でも問題はメインループじゃなくてufast loopの方なんだからいくらケツ動かしたって駄目だよね…

なもんで PR/42032として報告されるバグが発生し、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)];
 		}

おケツを超えてないことのチェックが追加されている。 でもこの修正って不十分だよね、まだufast loopに未練が残っててループのアンロールが残ってしまっている。

1回のsの移動でもおケツを超えてしまったならばそこはOOBなので、参照しようとしたら場合によってはSIGSEGVやSIGBUSでお亡くなりになるはずなんよね…

じゃあ正しい修正はどうすべきかというと、これはどうあがいても実装不可能なんだからまずufast loopを諦めるのが正しい。

diff --git a/lib/libc/string/bm.c b/lib/libc/string/bm.c
index a961cbb0ce6..d67f6c58965 100644
--- a/lib/libc/string/bm.c
+++ b/lib/libc/string/bm.c
@@ -163,60 +163,30 @@ bm_free(bm_pat *pat)
 u_char *
 bm_exec(bm_pat *pat, u_char *base, size_t n)
 {
-	u_char *e, *ep, *p, *q, *s;
-	size_t *d0, k, md2, n1, ro;
-	int rc;
+	u_char *e, *s;
+	size_t k, n1;
 
 	_DIAGASSERT(pat != NULL);
 	_DIAGASSERT(base != NULL);
 
-	if (n == 0)
-		return NULL;
-
-	d0 = pat->delta;
 	n1 = pat->patlen - 1;
-	md2 = pat->md2;
-	ro = pat->rareoff;
-	rc = pat->rarec;
-	ep = pat->pat + pat->patlen - 1;
-	s = base + (pat->patlen - 1);
-
-	/* fast loop up to n - 3 * patlen */
-	e = base + n - 3 * pat->patlen;
-	while (s < e) {
-		k = d0[*s];		/* ufast skip loop */
-		while (k && s < e) {
-			k = d0[*(s += k)];
-			k = d0[*(s += k)];
-		}
-		if (s >= e)
-			break;
-		if (s[ro] != rc)	/* guard test */
-			goto mismatch1;
-					/* fwd match */
-		for (p = pat->pat, q = s - n1; p < ep;)
-			if (*q++ != *p++)
-				goto mismatch1;
-		return s - n1;
-
-mismatch1:	s += md2;		/* md2 shift */
-	}
-
-	/* slow loop up to end */
+	s = base + n1;
 	e = base + n;
+
 	while (s < e) {
-		s += d0[*s];		/* step */
-		if (s >= e)
-			break;
-		if (s[ro] != rc)	/* guard test */
-			goto mismatch2;
-					/* fwd match */
-		for (p = pat->pat, q = s - n1; p <= ep;)
-			if (*q++ != *p++)
-				goto mismatch2;
-		return s - n1;
-
-mismatch2:	s += md2;		/* md2 shift */
+		/* fast skip loop */
+		while ((k = pat->delta[*s]) != 0) {
+			if (s >= e - k)
+				return NULL;
+			s += k;
+		}
+		/* guard test */
+		if (s[pat->rareoff] == pat->rarec &&
+		/* fwd match */
+		    !memcmp(pat->pat, s - n1, n1))
+			return s - n1;
+		/* md2 shift */
+		s += pat->md2;
 	}
 
 	return NULL;

はいコードもすっきりしたよね、ufast loopとslow loopのふたつのメインループがあったけど、fast loopのひとつに一本化できたし、goto も廃止することができた。

やたらと無駄な変数が多いのも古いコードなのでregister修飾子つけることで高速化を期待してたことの名残だから消しまくり、もはや今の時代無意味だし。

あと素のBM法やBMH法だとマッチしなかった場合の移動距離の算出に何文字目までマッチしたかが必要になるのだけど、Sunday法ではもはや必要ない情報なので、手書きループでマッチかけずともmemcmp(3)を使えばよろしい。 コンパイラくんが__builtin_memcmp()的なもので高速化してくれるのも期待できる、逆に遅くなってたら戻せばいいだけだ:-P

@bm(3)についてはデザインも微妙なんだよな…

プロトタイプu_char *(=unsigned char *)なのconst char *に変えたいよね、いちいち呼出し側でキャストするのめんどくせえ。 だってunsigned char *である必要性って、d0[*s]の一か所だけだもん。

あとわざわざ検索パターン文字列をコピーしてること、ポインタだけ持ってればいい話でね。 さらに移動距離のテーブルであるdeltaも固定長で宣言できるのにいちいちmalloc(3)してるし。

そもそもbm_pat型がbm.hで臓物見えてるのも気に入らないのだよな、こういうのは

typedef struct bmpat *bmpat_t;

みたいに不完全型にして実装見せるもんじゃないよねぇ、まぁ古いコードだからしゃーないけど。

これらの問題を修正しようとするとギリギリバイナリ互換は達成できそうでも、ソース互換無くなるからやっぱ変えられないので困る。 やっぱりオレオレN6では新しい実装入れて、bm(3)はobsoleteにしようかなという感じ。

*1:前回先頭一文字だけ検索パターン文字列のケツ1文字で後はゼロフィルと正しくない事を書いてしまったが、これはワイがなぜかmemset(3)とmemcpy(3)を見間違えたせい、斜めに読み過ぎて首が75°くらい曲がってない?大丈夫?

[宗教] ThinkPad X220 3号機逝く

今日になって電源すら入らなくなった、お前ら煽ったからって藁人形に五寸釘打つのを止めろ!(被害妄想)

ACアダプターを刺すとバッテリーランプは点滅するので、キーボードの問題が電源ボタンにまで進んだ感じやな。 なのでキーボードの疑いが高まったけど依然システムボード側かもしれない、犯人は20代から30代、もしくは40代から50代の可能性もある。

システムボードなら臓器移植の時間だね(ニッコリ)なんだが、問題はもはやX220のシステムボードってあまり売ってないんだよな、あってもX220iのi3とか。 やっぱりX230化しか無いのかね、7段キーボードは物理的にはつくけど認識しないキーがいくつかあって改造BIOSも無いのがネック。まぁ一番のネックはお金なんですけどねー。

2021/05/25(Tue)

[オレオレ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行目でやってる事は

を導き出す処理だということが判る。

ではもう一度この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というパラメーターがあって、これを事前に計算しておくことで検索パターン文字列と検索対象文字列の比較する長さを減らせるみたいなのだ。 なんかペーパーの信用度が個人的にガッツリ落ちてるので、実は計算するとコストは変わらない的なオチが待ってんじゃねぇのという疑惑を抱いてしまうが、そこも読んでいきたい。

*1:どうもSunday法というと1990年の A very fast substring search algorithmのQuick Search法の方を指すようで、bm(3)が実装している1991年の Fast string searchingとは全く違うものなので呼び方を改めた、ジミーウェールズからのメッセージをお読みくださいサイトにも情報無いので一般的にどう呼ばれてるか知らねえから。 なんせワイは情報処理の専門教育受けたことねーし、チャラい街の経済学部で日夜音楽を学んでたからな…

2021/05/26(Wed)

[オレオレN6] 続々々・bm(3)のバグのお話

新潮文庫の堀口大學訳サン=テグジュペリ「戦う操縦士」が電子書籍で格安で復刊してますね、えーっと紙は死んだ?(ニーチェ) いっとき紙の文庫は結構なプレ値してたんだよな、俺も大昔2kくらい出して買った記憶がする。みすず書房の「城砦」なんかが入ってる全集もしばらく前に復刊したけど今はもう入手困難かな。

あと久しぶりにフィルムの現像出しに行った先で、通常は4000円弱する純米吟醸酒の一升瓶が訳あり品(賞味期限5/31)で880円で売ってたので買ってみた。 普段安酒(イギリス労働者階級の不道徳な酒ことジンかロシア人のミネラルウォーターことウォッカ)ばかりで飽きてたからね、日本酒とワインはさっぱり判らんが甘くて美味しかった。

はいどうでもいい話はおいといて、前回はHume-Sunday法の4.2.4 guardを読み解いて、別にこれ文字の出現頻度テーブルなんて必要ないじゃんという結論に達し、 オレオレN6では消したところまで。

しかしですね、一晩寝てジンウォッカでなく純米吟醸酒で酔っ払った頭でもう一度このロジックについて考え直したところ

ことにはたと気づき、確率論的には勝ち目のある勝負なんだなぁと考えを改めた。いかんですねワイの脳味噌アルコールで死んでますね…まぁ賭け事クッソ弱いからしゃーない人生負け続け。

ただしこの投機的実行のアテが外れた時はループに突入するペナルティあるわけで、相殺したら大して差は無いのでは?という気がしないでもないけどなぁ。 やっぱり実際にテストデータ用意して検証しない事にはわからんくらいパラノイアな高速化なのである。

ほんとに微妙な差だと思われるので、それならfreqテーブルの国際化のコストと、実装の問題で検索パターン文字がINT_MAXより長いケースでinteger overflow起こすこと考えると、消して正解なのでは感はある。

うーんめんどくせえ、C++のboyer_moore_searcherとかboyer_moore_horspool_searcherとかどうしてんだろ。

@BM法の基本を理解する

前回Hume-Sunday法の4.3 Shift functionの解説するよと書いたけど、そもそもBM法の基本を解説しておかないとわけわかになりそうなのでそっちを先にやる。いかがでしたか?この広告をクリックするかSNSでフォローして応援してね!(広告も無いしSNSもやってない)

そいやBM法で検索して引っかかるような解説だとたいてい例題に英文を使ってるので日本人に優しくないよねあれ。 俺は何十年C書いててもfcntl.hとfctrl.hのtypoに気づかずコンパイルエラーの原因がわからず3秒くらい悩むので、英単語がマッチしてるかなんてわからないのだ。

これはBM法がマルチバイトに対応してない関係上サンプルコード書く時に困るから仕方がない面もあるのだが、ワイド文字であれば(実装の困難さはさておき)理論上問題ないので、国際化の話題を多く扱う当チラシの裏においては例題は日本語を使って解説していこうと思う。 ちなみに最初は「ぬめねわはほま」とかのゲシュタルト崩壊必至な文字のみで解説しようと思ったけど、実際に書いてる方がゲシュタルト崩壊して解説が辛くなったので断念した。

では例題としてBM法で「おまーんこくさいくうこう」から「くさい」を検索してみようと思う、くさそう。

最初に検索パターン文字列の末尾一字が一致するかをチェックする。

おま|ー|んこくさいくうこう
くさ|い|
   ↑不一致

不一致であれば移動を行う、ナイーブ法なら単純に1つ後ろにずらすだけだが、BM法では移動距離を不一致な文字がパターン中に存在するかしないかで決定する。

  • 存在する … 移動量はパターンの末尾からその文字が出現するまでの距離
  • 存在しない … 移動量はパターン長

「ー」は後者なので移動量はパターン長つまり今回は3となる、この移動距離がナイーブ法より大きくできる事が高速文字列検索のキモなのである。

それでは3移動してみよか、移動したら前回と同様に末尾一字を比較するよ。

おまーんこ|く|さいくうこう
   くさ|い|
     ↑不一致

不一致文字の「く」はパターン中に存在する文字、この場合の移動量は前述の通りパターンケツの「い」から「く」までの距離で2となる。

そんでは2移動する。

おまーんこくさ|い|くうこう
     くさ|い|
        ↑一致

末尾「い」が一致したので、そこから前方に戻ってパターンの頭までの比較を行う。

おまーんこく|さ|いくうこう
     く|さ|い
       ↑一致

おまーんこ|く|さいくうこう
     |く|さい
      ↑完全一致

はい、完全一致なのでここで検索終了。たぶんイソプロピルアルコールの情弱殺処理試験で求められるBM法の知識はこの程度でいいはず。

この末尾の不一致文字を元に移動量を計算する方法を「不一致規則(Bad Character Rule)」と呼ぶ、コードを最適化するために事前にテーブルを作成するのが一般的で、Hume-Sunday法のペーパーではこの部分やね。

#define ASIZE 256

static struct
{
	int patlen;
	unsigned char pat[1024];
	long delta[ASIZE];
	...
} pat;

void prep(unsigned char *pb, int len)
{
	register unsigned char *pe;
	register int j;
	register long *d;

	pat.patlen = len;
	assert(pat.patlen < sizeof(pat.pat)); /* true or abort */
	memcpy(pat.pat, pb, pat.patlen) ; /* store pattern */
	/* get skip delta */
	for(j = 0, d = pat.delta; j < ASIZE; j++)
		d[j] = pat.patlen;
	for(pe = pb+pat.patlen–1; pb <= pe; pb++)
		d[*pb] = pe-pb;
	...

}

@次回予告

末尾1文字は一致したけれども前方比較の最中に不一致があった場合の移動量はどうしたらいいかだ、この時どれだけ移動できるかがBM法の改良の歴史なのである。

ちたまにあふれるBM法の解説ではそのまま不一致規則を使って移動を行うものが多いのだけど、正式版のBM法では「一致サフィックス規則(Good Suffix Rule)」というものを使う。 これは結構ややこしくて計算自体がコストになったりするのでいくつかの改良法が提案されてる。それについて飽きてなければ次回説明するでしょう(飽きてる)。