DFA で a(.*)b

正規表現から非決定性状態遷移機械 (NFA) を作成することができ、 NFA は決定性状態遷移機械 (DFA) に変換することができる、 という説明での正規表現は kleene が扱った正規文法の表記方法に対応しているものであってピュア正規表現とでも呼んだ方がふさわ…

HTTP Digest 認証の SHA-256 の扱い

HTTP Digest 認証で SHA-256 を使うための動きをメモ。 動きを見ていく要点は、 algorithm=SHA-256 の表記のぶれで、 ドラフトの初期では SHA256、 途中で SHA2-256 と変わり、 現時点では SHA-256 に落ち着いています。 SHA-256 を使った、response の求め…

キャプチャ注釈付き DFA の作り方私案

2015 年 9 月 14 日 この稿のやりかた、 キャプチャ対象ごとに遷移先状態を別に分ける方法は、 もはや利用していません。 今は、アクション表を使い、 遷移元状態と文字クラスの組み合わせに対してアクションを実行するようにしています。 これまで、HTTP/1.…

GNU libc 4.9/mbsnrtowcs と LLVM libc++

この件はとりあえずながら解決しました。GNU libc 4.9 の mbsnrtowcs は __GCONV_INCOMPLETE_INPUT のとき、codecvt::do_in() が期待している (size_t)(-1) ではなく、ゼロを返します。そのため、do_in() が partial にするべき場合に ok を返してしまい、in…

Knuth 先生の乗法ハッシュ

Deflate アルゴリズムの実装の一つとして、Plan9 の libflate の deflate.c のソースコードを読んでいました。 LZSS 法の最長一致探索をするために 3-GRAM からハッシュ値を求めて、チェイン法を使っています。さて、そのハッシュ値の求め方なのですが、抜粋…

RFC1951 Deflate フォーマット

Deflate のフォーマットは出回り始めたころに一通り調べたのですが、20 年以上前のことなので、細部を忘れてしまっていました。そこで、復習兼ねて、Ruby で内容をダンプするプログラムを書いてみました。Deflate を含んでいる圧縮データを作るのには gzip …

LLVM libc++ の stream_buf の underflow

Linux の LLVM libc++ で、ja_JP.UTF-8 を std::wcin に指定して漢字かな交じりのテキストを読み込ませようとしてもうまくいかず、マルチバイト文字の先頭バイトで eofbit (とfailbit) が立ってしまうことがあります。⇒ その後、動きあり「LLVM libc++ で UT…

m4/macro の OCEK 状態遷移

m4/macro はリーダ・マクロ・プロセッサに該当します。これをCEK マシンの観点から見て、どのようにコントロール (C)、環境 (E)、継続 (K) が状態遷移するのかチェックします。コントロールに相当するのは、入力ストリームです。さらに、マクロ・プロセスは…

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

戻り読み (lookbehind) をどう実装するか試行錯誤している最中です。処理の効率はともかくとして、今のところ楽そうな実装は、正規表現の連結を右から左へと逆順にコード生成し、仮想マシンの実行時に文字ポインタも文字列の先頭側へ逆方向に戻すやりかたで…

スワップを使ったブロック移動

Thompson と Ritchie が書いた UNIX ed(1) は 1972 年に PDP-11 アセンブラで記述されたものがアーカイブで辿れる古いもので、基本的な部分はその版から変化していません。というよりも、軽くショックを覚えるのは、アセンブラで書いてある方が C 言語で書い…

Myers 法の編集グラフ・グリッド

2 つのテキストの差分を求める王道アルゴリズムの一つである Myers 法を使って、編集グラフ・グリッドを求めて表示するネタ・プログラムを書いてみました。Myers 法は GNU diff 等が採用している方法で、Myers 法そのものはレーベンシュタイン距離を求める手…

ed (1) コマンドのアドレス構文

行テキスト・エディタ ed (1) コマンドの行を指定するアドレスの構文を LR(1) 文法で書いたらどうなるのか、試していました。アドレスは、絶対アドレスと現在の行 (ドット) からの相対アドレスが利用でき、プラスとマイナスの記号でつないでいくことができま…

std::move の働き

私は C++11 の右辺値参照とそれに関連する仕組みの理解が甘くて、値渡しの実引数を std::move でキャストすると何がおきるのか即座にわからなかったので、試してみます。 #include <iostream> #include <algorithm> #include <memory> struct sv { int* p; int n; sv () : p (nullptr), n </memory></algorithm></iostream>…

UTF-8 デコード用オーバーラップ読み込みバッファの試み

R7RS Scheme の入出力では、read_char で入力ポートから UTF-8 をデコードし、Unicode のコードポイントを返す必要があります。入力ポートをバッファリングするとして、UTF-8 シーケンスがバッファの末尾と次に読み込む範囲にまたがっている場合がありえます…

Schönhage-Strassen の modulo その2

Ruby 版を C99 に直訳してみたところ予想外に速度が劣っており、原因を調べるためにプロファイルをとったりしてみたところ、カラツバ乗算よりもフーリエ乗算の方が 32 ビット同士の乗算実行回数が数倍多いことに気がつきました。不必要に大きな精度で計算し…

Schönhage-Strassen の非再帰・FFT の例

昨日の離散フーリエ変換で書いた例を、高速フーリエ変換 (FFT) に書き直します。GNU MP の mpn/generic/mul_fft.c では重み付きの離散フーリエ変換 (Discrete Weighted Transform) を使っていますが、この例では重みなしのストレートな離散フーリエ変換で計…

Schönhage-Strassen の非再帰・非 FFT の例

昨日の結果の検算を兼ねて、Schönhage-Strassen の modulo を使い、非再帰、非 FFT な例を作ってみます。非再帰なので、小さな桁の数のかけ算とし、128 ビットの数同士のかけ算を考えます。 a = 0xb179d8d22332abd09def7dfdb8451405 # integer_length(a) == …

Schönhage-Strassen の modulo

BASE**n + 1 を法に選ぶと、BASE の n 乗が -1 になり、BASE**2 の n 乗が 1 になる性質から nega-cyclic たたみ込みになることを、前回までのエントリで試してきました。これまで BASE = 10 の特殊なケースを試してきたのですが、これからは本来の Schönhag…

Schönhage-Strassen の巡回たたみ込みバタフライ演算

Schönhage-Strassen は nega-cyclic 巡回たたみ込みを利用して効率良く整数環離散フーリエ変換をおこなうことができます。これを高速フーリエ変換に組み込みましょう。最初に、配列 a の各整数値を、基数 base で桁単位に分解します。型を指定する言語の場合…

Schönhage-Strassen の高速フーリエ変換 (暫定)

昨日のエントリの末尾にある離散フーリエ変換に使う行列の内容から考えて、高速フーリエ変換には Sande-Tukey 法のバタフライ演算を使います。ところで、今回は 100 進数で計算経過を眺めるため、2 のべき乗進数向けの nega-cyclic な巡回桁ずらしを実装して…

Schönhage-Strassen の巡回たたみ込み

Schönhage-Strassen アルゴリズムのポイントは、位取り基数が base**2 で n 桁のとき、法が base**n + 1 のもとで base の n 乗が 1 と合同になり、base が位相回転子になることでした。 base = 100 n = 8 modulo = 10**n + 1 (0 .. n).map{|k| base**k % mo…

Schönhage-Strassen 法の例

英語版 Wikipedia のページに例として記載されている図は、一般の整数環離散フーリエ変換を使った整数乗算になっているため、Schönhage-Strassen の例を作ってみます。ただし、高速フーリエ変換ではなく、遅い離散フーリエ変換をおこない、それも富豪的に合…

英語版 Wikipedia の Schönhage-Strassen 法の例の検算

10 進数で 1234 * 5678 == 7006652 となる例を、Ruby を使って整数環離散フーリエ変換 (高速フーリエ変換ではなく) で検算してみます。⇒ http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm2014年10月22日: 位相回転子のべき乗を各項…

桁ずらし除算の算数

スクールブック除算と再帰除算の qhat と rhat を求める手順が、これまで書いてきた次のやりかたで良い根拠をまとめます。スクールブック除算の場合。 uint32_t qhat; uint64_t rhat; if (u3 < v2) { uint64_t const uuhat = (uint64_t)u2 + ((uint64_t)u3 <…

Plan9 libmp のカラツバ乗算

Plan9 libmp はカラツバ乗算を利用しています。どのように途中結果を求めたり一時領域に保存するのか、オープンソース版のソースを読んで調べてみました。⇒ https://github.com/brho/plan9/blob/master/sys/src/libmp/port/mpmul.cPlan9 libmp の多倍長整数…

符号なし加算の桁あふれと符号なし減算の桁借り

C 言語のほとんどの実装は、符号なし整数を剰余項として扱うだけで、桁あふれの発生を通知する機構を持つ数値型を提供していません。剰余項の加算の桁あふれは範囲チェックをすり抜ける原因になり、桁あふれを無視したことがセキュリティ・ホールになった事…

Ephemeron - ハッシュ表とコピー・コレクタによる実装

揮発性 key-value マップである「Ephemeron Table」をハッシュ表とコピー・コレクタで書いたので、要点を備忘録として残しておきます。ハッシュ表にオープン・アドレス法を、コピー・コレクタに Cheney 法を採用しています。オープン・アドレス法にしたのは…

R7RS の構文を実装向けに解析表現文法で書き直し

Revised 7 Scheme 2. および 7.1. の read 手続きの入力構文を、実装向けに書き直します。R7RS 文中の説明も解析表現文法に盛り込むことにします。構文は外部表現の datum から始まります。7.1.1 の記述によると、論理値・文字・数値・縦棒記法でない識別子…

svm.c で動かすための階乗再帰版のハンド・コンパイル

svm.c には階乗の再帰呼び出しとループの2通りで計算する手続きを、それぞれハンド・コンパイルとハンド・アセンブルして C 言語のソースコードに埋め込みました。ここでは再帰呼び出し版のハンド・コンパイル手順をまとめます。 (define (factrec n) (if (<…

A 正規形 CEK マシン・ベースの仮想マシン

Scheme コンパイラ向けの A 正規形 CEK マシン・ベースの仮想マシンを考えます。この手のものでは、Peter Henderson が 1980 年に発表した Lispkit Lisp の SECD マシンをベースにしたスタック・マシンが有名です。基本方針は、Henderson の仮想マシンになら…