「ソフトウェア作法」40周年を過ぎて

旧聞に属す話。 昨年 (2016) は名著 Kernighan & Plauger Software Tools (1976) の出版 40 周年でした。 それを意識して題材を選んできたエントリをまとめておきます。 やったことは、 Unicode への対応と、 40 年間で生まれたより良いアルゴリズムへの変更が主です。 7 章だけは題材を簡易 roff から Markdown へ変更しました。

「1.2 文字数を数えること」関連

Unicode の文字数カウント

UTF-8 用 wordcounter

Unicode の時代になって、 文字数を数えること一つをとっても簡単にいかなくなりました。 Unicode では複数のコードポイントを組み合わせて一文字にできる、 合成文字と異字体同位体が利用できます。 プログラミング言語では Swift が標準ライブラリで合成文字等を認識できて文字単位の処理ができるようになっていますけど、 C++11 では自力で Unicode Character Database を頼りに文字へ分解しないといけません。

「1.5 欄飛ばしの除去」関連

ucd::width 関数 (その1)

wstring な detab

端末用の固定幅の文字フォントに限ると、 Unicode では East Asian Width 問題があるため、 タブを空白文字へ展開して期待した結果を得るのにも一苦労します。

「2.4 文書情報の圧縮」関連

cxxgzip-cxx11: RFC 1951 Deflate examination on C++11

cxxgzip - gzip(dump)?.rb から C++11 への意訳版

圧縮技術も 40 年間で様変わりしました。 この書籍は連長圧縮のコード例が説明されているだけです。 20年以上の実績がある Deflate は、 3 つの圧縮手法を組み合わせて作られています。 LZSS 圧縮、 長さ制限ハフマン符号、 連長圧縮です。 私の実装では、 長さ制限ハフマン符号の生成に Package-merge アルゴリズムと、 LZSS 圧縮のハッシュ表のために D. Knuth 乗法ハッシュを使っているのが特徴です。

「2.6 暗号化」関連

AES 共通鍵暗号

AES-GCM - Galois/Counter Mode を 4 ビット単位乗算に

RFC 4493 AES-CMAC アルゴリズム

RFC 5297 AES-SIV モード

RFC 7539 ChaCha20 暗号

暗号技術は 40 年間で飛躍的に発達しました。 暗号技術は 10 年単位でリプレースが進み、 今の時点では共通鍵暗号は認証モード付きストリーム暗号 AES-GCM を使うことが求められています。 ただし、 ストリーム暗号には利用上の注意点があり、 それをカバーする目的で AES-SIV モードが提唱されています。 共通鍵暗号の認証付き暗号モードでは、 他の組み合わせ ChaCha20-Poly1305 も SSH などで利用されています。

RSA 暗号 EM-OAEP

公開鍵暗号では、 RSA 暗号の特許保護期限が終わり、 確率論的な巨大素数判定法が開発され、 安全なパディングが開発されてと、 周辺技術が揃って利用しやすくなりました。 現在は 2048 ビットの鍵長が求められ、 ビット長が長すぎる用途では楕円曲線暗号の利用が進んでいます。 ただし、 楕円曲線暗号は特許の問題がグレーなので、 ここでは取り上げていません。

digest::sha::sha256

digest::sha::hmac_sha256

暗号と組み合わせて利用されている暗号論的ハッシュ関数は世代交代が進み、 SHA-256 以後の利用が推奨されています。

「2.7 文字の置換」

wchar な translit コマンド

これは C99 で書いてたもので、 C++11 には書き直していません。 日本語の tr 処理は、 perlruby でも可能ですが、 文字列エンコーディング指定が必要になってからワンライナ向けでなくなってしまいました。 句読点の一括変換等に良く使っています。

「問題 2-27 tail を書け」

tail

ファイルをオープンした時点の末尾 n 行を書き出すだけのコマンドです。 tail コマンドの便利な機能にオープンしたままで行が追加されたことを検出して画面に表示する機能がありますけど、 手が回らず。

「3.1 ファイルの比較」関連

udiff-cxx11: word based unified color differences between two texts

unified format diff between texts line by line

Hirschberg法 - Wu による O(NP) テキスト差分の試行

3 方向マージ出力

テキスト差分計算技術も 40 年間で発展した分野です。 今やなくては済ませられない重要な技術になりました。 現在広く利用されているのは Myers 法にメモリ利用量を抑える Hirschberg 法を組み合わせたアルゴリズムです。 Myers 法の後に登場した、 さらに効率の良い Wu 法があるのですが、 Hirschberg 法との組み合わせの成功例が乏しく、 Myers 法ほどには一般化していません。

Wu 法と Hirschberg 法の組み合わせに成功したのが、 私のこの 2 年間の最大の成果です。 成功の要点は Wu 法のオリジナルのアルゴリズムを Hirschberg 法向けに手直ししたこと。 2 つのアルゴリズムを組み合わせる実装の見通しが良くなり、 この組み合わせ特有の問題点の原因をあぶりだすことができました。 そうして、 差分処理コマンドに使える実装にたどり着けました。

less もどきのための行分割処理

これ以外にも 2 章と 3 章のいくつかの題材は、 less に似たプログラムの中に組み込んでいます。

「4.4 クイック法」

sort - sort lines of text from stdin to stdout

イテレータによるマルチキー・クイックソート

テキスト・データを対象とする整列法は生物情報学の DNA への応用へ向けて発達が続いていました。 そのためには、 行頭に同じ文字列が並ぶ巨大修辞句配列の高速整列が不可欠で、2009 年の 修辞句配列専用の Induced ソートが発表されるまで、 様々な手法が研究されてきました。

クイックソートを改良したマルチキー・クイックソートは、 そうした動きの初期に生まれた整列方法です。 こちらは通常のテキストの整列にも利用できます。 これを使った行単位の整列プログラムを書いてみました。

「5 章 文型の照合」

t42::wregex

t42::wregex のエンジンを Russ Cox による RE1 ベースに変更

t42::wregex 用の戻り読みのアイデア

正規表現のエンジンも 40 年間で発達しました。 現在広く利用されている正規表現エンジンは、 照合パターン中のいくつかある選択肢の中で左側から順に照合できるだけ進めていって失敗したら次の選択肢を試すやりかたになっています。 一方、 ベル研究所では対象文字列を一文字ずつ照合していく方法を 2 通り開発し、 一方はプログラミング言語の字句解析部エンジンに利用されています。 Rob Pike がもう一つ開発し、 それを近年 Russ Cox がさらに改良したものを Google RE2 エンジンが利用しています。

これは Russ Cox RE1 をベースに、 Perl5 正規表現からバックリファレンス、 先読みを追加したものです。 この実装の目玉は文字単位の戻り読みをおこなっているところで、 文字列の先頭へ向けて逆向きにパターン・マッチングをおこないます。 正規表現オプションの ms が常にオンの場合の動作をし、 オプション x には未対応です。

「6 章 文書編集」

edit-cxx11: traditional line-oriented text editor.

edit-cxx11

コマンドのアドレス式を sam の表記へ変更し、 正規表現Perl 5 に近づける改良をしてあります。 無制限 undo できる対話的な行単位テキスト処理系として perl ワンライナや sed と使い分けて使っています。

「7 章 文書整形」

markdown-subset-cxx11: C++11 Markdown Subset to HTML converter

Markdown サブセットから HTML へのコンバータ

Markdown も文書整形の一種です。 限定版 roff を再実装しても使い道を思いつかなったので忘れることにしました。 Markdown は手強い構文解析対象で、 リファレンスのふるまい記述を満足させるだけでも苦労します。 この実装では、 テキスト・エディタの行バッファを援用して、 少しは効率よく動かせるようにしてみたのですが、 複数行で一段落になる場合等に行連結が残っていて、改善の余地があります。

「8 章 マクロ処理」

Christopher Strachey's General Purpose Macrogenerator (GPM)

macro

macro マクロ処理

GNU m4 の骨格は本書籍のマクロ・プロセッサであると man ページに書いてあります。 m4 をあまり使う気になれないのは、 クォートの付け方がわかっていないと使い物にならない面倒さがあります。 文字列マクロとクォートの切っても切れない面倒な関係は、 元祖マクロ・プロセッサ GPM からの伝統です。 このマクロでは、 ワイド文字列をマクロ名とクォート記号に使えるようにしてあり、 マクロ記述とリテラルを視覚的に分離できるようにしてみました。