Android 7 Nougat と jemalloc

binonicのソースツリーを見ると, Nougatにjemallocがある.
dlmallocから置き換えたってことかな.

Visual Studioの文字列リテラルの文字コードを設定する

#pragma execution_character_set("utf-8")

と書くと翻訳単位毎にリテラルの文字コードを設定できる.

さらに, clのオプション/FIは, 全てのソースファイルに対して強制的にインクルードするファイルを指定する.
forceinclude.hに, execution_character_setを書いて,

cl.exe /FIforceinclude.h

とすれば, やりたいことができるんじゃないかな.

Markdown をプレビューする

MarkdownPreview
MarkdownSharpと.NetのWebbrowserを使ってプレビューを試みる.
Markdownをプレビューするだけの機械.

カンファレンスのメモ取りに, Markdownを使おうとしたことがあった.
しかし, スタンドアロンのエディタに満足できそうなものがない.
VimのMarkdownプレビューも試したが満足できなかった.

時間ができたので作ったよ.
気に入らないところがあれば好きに弄るがいいです.

LOUDSでTrieを作る

LOUDSを用いたTrieです. 文字列をキーとした連想配列で使用することを想定しています.
Trieと 完備辞書はこのために作成しました.
上２つは公開時から不具合修正と機能追加をしています.

LOUDSは, 木構造をビット列で表現します.
節点を幅優先で走査し, 各節点で子の数だけ"1"を並べ, 節点の終端に"0"を置きます.
子のない節点は"0", 子が１つの節点は"10"です.

完備辞書

完備辞書そのものの説明は, ネット検索か,
高速文字列解析の世界<Amazon>で確認してください.

ビット列$B[0,n]\ B[i]\in\{0,1\}$
について, 以下の操作を実現する.
$access(B,i)\ B[i]$を返す
$rank_{b}(B,i)\ B[0,i)$中の$b\in\{0,1\}$の数を返す
$select_{b}(B,i)\ B$中の$i+1$番目に出現した$b\in\{0,1\}$の位置を返す

Trie

トライ木と呼ばれるデータ構造を作成します.
retrievalからtrieなので, treeと同じ発音だそうですが, 日本語ではトライだそうです.
各ノードがそれぞれラベルを持ち, 部分木は共通の接頭辞を持ちます.
"add", "and", "ans"からなるトライ木は以下のようになります.

前処理のための中間データとして作成したため, 効率は考慮していません.

population count

32bitのpopulation count
1のビットを数え上げる
コンパイラ組み込み関数を使わない場合,

inline u32 population_count(u32 v)
{
    v = (v & 0x55555555U) + ((v>>1) & 0x55555555U);
    v = (v & 0x33333333U) + ((v>>2) & 0x33333333U);
    v = (v & 0x0F0F0F0FU) + ((v>>4) & 0x0F0F0F0FU);
    v = (v & 0x00FF00FFU) + ((v>>8) & 0x00FF00FFU);
    return (v & 0x0000FFFFU) + ((v>>16) & 0x0000FFFFU);
}

gccの組み込み関数,

int __builtin_popcount(unsigned int x)

VCの組み込み関数,

unsigned int __popcnt(unsigned int value)