BASE 64/32 を 32/64 ビット回転に改訂

2 年前に C++11 で書いた BASE64 と BASE32 エンコーダのビット回転をワード幅でおこなうように改訂しました。 これまでは、 BASE64 で 24 ビットのビット回転をおこなっていました。 そのため、 コンパイラがビット・シフト命令とビット論理和命令を生成し…

RFC 5322 のコメント

電子メールのヘッダ中で、 利用しようと思えば利用できるものの、 利用されるのが稀な記法の一つに、 入れ子のコメント、 およびコメント中でのエスケープがあります。 コメントは丸括弧で囲み、 コメントの中にコメントを入れ子にすることができます。 さら…

JSON デコーダ (Wirth の表制御型構文解析法)

Wirth 教授の表制御下向き構文解析器に合成属性を組み込んで JSON のデコーダとします。⇒ https://gist.github.com/tociyuki/04875e7c78e86b701daca803c0c80789文字エンコーディングは UTF-8 入力エンコーディング、 UTF-8 内部エンコーディングとします。 J…

Wirth の表制御型構文解析法

N. Wirth 著 ALGORITHMS+DATA STRUCTURES=PROGRAMS (1976) の表制御型下向き構文解析プログラムを少しアレンジして仮想マシンにしてみました。 なお、 現在の版では、 この方式の説明は大幅に省略されているものの、 さわりを知ることができます。⇒ https://…

POSIX シグナルを捉える self-pipe トリック

Gtk+ がイベント・ループに使っている GMainContext は「POSIX シグナルの GSource イベント化の実装読み」のように、 スレッドで POSIX シグナル通知フラグを転記する凝ったやりかたを採用しています。 イベント・ハンドラを動かすスレッドでシグナル通知フ…

低解像度折れ線グラフの実線と点鎖線の認識の試み

ウェブ・ページに埋め込まれた棒グラフや折れ線グラフからデータを読み取りたいときがたまにあります。 例えば、 東北沖大地震の年の夏、 東京電力管内で電気の使用制限が求められた当初、 東京電力がウェブ・ページに棒グラフを掲載して電力使用量をアナウ…

メッセージ・ヘッダ風のフロントマター

Markdown の前にブログ生成等のふるまいを記述するフロントマターには、 YAML をはじめとして、 いろんな形式が使われていますが、 メッセージ・ヘッダ風の簡略なものでも良いのではないかとスキャナを書いてみました。 YAML はスラッシュ 3 つで区切ります…

2D プロット・グラフのデータ・マークの数値化 (その4)

目盛の数値を読むことができたので、 データ・マークの位置を目盛に合わせて読み取れるようにします。 ⇒ tociyuki/unplot2d-cxx11: from plot2d to numerical values (experimental works)その 3 でオングストロームを認識できてなかったので、 横軸をナノメ…

2D プロット・グラフの目盛数字とラベルの認識 (その3)

データ・マークから数値に変換するには、 グラフの縦軸・横軸の目盛に打ってある数字列を読み取って数を求めておく必要があります。 さらに、 そのデータがどのような物理量かを知るためには縦軸・横軸のラベルを読んでおかなければいけません。 ラベルに単…

2D プロット・グラフの横軸目盛の認識 (その2)

グラフの枠の付属物である目盛の位置を検出します。 枠の下辺である横軸がリニア・スケールであるとして、 目盛を読んでみます。画像の特徴としては、 等間隔で同じ形状の目盛が並ぶこと、 目盛の個数が少ないこと、 目盛が短いこと、 データ・マークが大き…

2D プロット・グラフの枠線の認識 (その1)

これは、 主に科学技術論文に掲載されているグラフから数値を復元する試みの初めの一歩です。 初めの一歩だけに、 問題をシンプルにして、 PNG に描いたモノクロ 2 値ロスレス圧縮・歪みなし・モアレなし・ノイズなしという最も扱いやすいグラフの画像からの…

Hopcroft 法で DFA 最小化

DFA の最小化の代表的なアルゴリズムは Hopcroft 法です。 終状態とそうでない状態に 2 分割しておいてから、 さらに分割を進めていくのは Moore 法と同じですが、 再試行なしで幅優先で分割を進めていくため、 理論上の最悪計算量はΟ(n log n) です。 とい…

DFA 状態の最小化

正規表現から DFA を直接生成すると、 NFA から DFA を作るよりも状態数が少なくなる傾向があります。 しかしながら、 最小の倍以上に状態数が増えて冗長になることもあります。 ⇒ Core regular expression to Deterministic Finite Automata, DFAそのような…

e+ と e? も DFA へ直接変換

「正規表現から DFA への直接変換」を拡張して e+ と e? も DFA に変換できるようにします。 e+ は 1 回以上の e の繰り返しで、 ee* と同じです。 e? は e があるかないかで (e|) と同じです。⇒ Core regular expression to Deterministic Finite Automata,…

正規表現から DFA への直接変換

Aho 等 COMPILERS PRINCIPLES, TECHNIQUES, AND TOOLS 2007 (ドラゴン・ブック) 3.9 節の前半、 「正規表現から DFA への直接変換」を C++11 で書いてみました。 単純化した正規表現から DFA 遷移表を作ります。 コマンドライン引数に与えた正規表現から作成…

トライ木主導の字句解析器の試行

プログラミング言語 Oberon-0 の字句解析をトライ木をメインに使うやりかたで書いてみました。この言語は多数のキーワードが定義されていて、 トライ木はキーワードと記号にマッチするように作ってあります。 キーワードの途中で失敗したときに、 識別子とし…

SipHash-1-3

ハッシュ表用の文字列のハッシュ関数に SipHash が主流になった当初はラウンド数が 2-4 の使い方だったのですが、 2015 年末に Rust がラウンド数を 1-3 に切り詰めてから、 Perl5 *1 と Ruby も昨年末に、 Python も今年の 2 月始めにラウンド数を減らしま…

PASCAL 系数式用演算子優先度構文解析器

発端は 1976 年に発表された 8080 プロセッサ用 Palo Alto Tiny Basic アセンブリ・出力リストを見つけて読んでいたときに、 これの数式の構文が PASCAL 系言語と同じだと気がついたときに遡ります。 再帰下降型の数式解析器ではポピュラーな構文で、 上向き…

行指向 HTML5 タグ用の正規表現エンジン

これは HTML5 タグを行指向でタグの前のインデント空白列と、 タグの後の行末空白と改行コードも含めて行全体にマッチングさせたい用途向けに組んだ、 特定パターン専用の正規表現エンジンです。 タグ名と要素の文字位置をリストアップすることができます。…

符号付き整数加減算のオーバーフロー・フラグ

いにしえの話ですけど、 8 ビット・プロセッサで最初に普及したインテル 8080 プロセッサには、 2 の補数表現での符号付き整数加減算にオーバーフロー・フラグがなく、 符号なし整数加減算の桁あふれを表すキャリー・フラグしかありませんでした。 そのため…

コンポーネント方式 mustache テンプレート

おもちゃ CGI (Common Gateway Interface) プログラム、 一行掲示板 suzume.cgi、 の改訂を年末から少しずつ進めている最中です。 このプログラムは、 C++11 で小規模の CGI プログラムを手軽に作る実験場で、 最低限の部品を組み込んであります。 当初から…

ジャーナリング付き入出力クラス (その4)

このエントリで、 ioblock_type の備忘録は終わりです。ioblock_type はデフォルト・コンストラクタだけで、 それでメンバを初期化します。 #include <map> #include <string> #include <utility> #include <algorithm> #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> #include <unistd.h> ioblock_type::ioblock_type (</unistd.h></fcntl.h></sys/stat.h></sys/types.h></algorithm></utility></string></map>…

ジャーナリング付き入出力クラス (その3)

メモリ中のバッファ・キャッシュに残っている上書き内容をジャーナリング・ファイルへ吐き出す journaling メンバ関数の機能に加えて、 それに続いてジャーナリング・ファイルへの記録をスナップショット・ファイルへ反映するメンバ関数もあって、 data_flus…

ジャーナリング付き入出力クラス (その2)

ファイルのオフセットを指定して、 そこから指定バイト数を読み出す data_read メンバ関数は、 読み出し範囲が含まれるブロックのキャッシュを調べて、 キャッシュされていないときは、 block_underflow メンバ関数で内容を読み取ります。 読み取った内容か…

ジャーナリング付き入出力クラス (その1)

アプリケーション組み込みのデータ・ストアを書くのに、 ジャーナリング付きの低レベルの入出力クラスがあると便利かもしれないと思いついて正月明けから作りだしたのですけど、 予想よりも複雑になってしまい、 これを使っていくかどうか自分に疑問を覚えつ…

ストレージ・アロケータのエクステント・ツリー操作

最近の巨大ストレージ対応ファイル・システムは、 フリー領域の管理をエクステント・ツリーでおこなうようになっています。 現在入手が容易な数 TB のディスクの場合、 伝統的なビットマップでフリー領域を管理しようとすると、数十から数百 MB が必要で、 …

非カーネル用のスラブ・アロケータ

オペレーティング・システムのカーネルのオブジェクト・キャッシュとして利用されているスラブ・アロケータは、 単なる高速なアロケータではなく、 割付・初期化済みのオブジェクトを alloc して、 free の時点ではデストラクタを動かさずに、 次の alloc で…

RFC 7230 HTTP/1.1 の Content-Length

Content-Length ヘッダは、 10進数の数字列 1 個だけを値に持つべきなのですが、 RFC 7230 では特殊な場合として、 コンマで区切った同じ数値を表す複数の数字列が並んでいても良いということにしてあります。 これは Content-Length ヘッダが複数ある場合を…

MurmurHash3 32 ビット char const* 用

今度は char const* 用の関数を作ります。 std::uint32_t murmurhash3_32 (std::size_t const len, char const* const str, std::uint32_t const seed = 0); 昨日の MurmurHash3 32 ビット版は std::string の文字列本体がほとんどの場合 4 バイト・アライン…

MurmurHash3 の 32 ビット版

MurmurHash3 の 32 ビット版を書いてみました。 // MurmurHash3 was written by Austin Appleby, and is placed in the public domain. #include <cstdint> #include <string> uint32_t murmurhash3_32 (std::string const& str, std::uint32_t const seed = 0); 文字列を 4 </string></cstdint>…