melancholic afternoon

プロシン補足その1

「Xbyakのシンタックスはmov(eax, ecx);で丸カッコはC++上無くせないよね」と発言したのだけど, 超絶技巧の遠藤さんにマクロ使えばできない?と言われたので少し考えてみた. で, こんな感じにはできた. というわけでカッコつけないプログラム第2段.

#include <???>

int main()
{
    mov eax, ecx;
    mov ecx, 5;
}
>./a.out
mov eax, ecx
mov ecx, 5

ここまでくるとセミコロンも邪魔だ(これは流石に消せない…よなぁ).

中身はたいしたことはしてない. まずmovなどの複数オペランドを持つ命令をマクロ定義にして最後にコンマを付与する.

#define mov Mov(),

あとはMovクラスに対してコンマ演算子(,)をオーバーロードしてデストラクタで処理するようにすれば終わり.

# 上記の例のようにprintするだけなら要らないけど通常は複数のオペランドが確定しないと評価できないのでデストラクタで行う.

#include <stdio.h>
#include <vector>
#include <sstream>

struct Reg {
    int idx_;
    Reg(int idx) : idx_(idx) { }
    std::string toString() const
    {
        return idx_ == 0 ? "eax" : "ecx";
    }
} eax(0), ecx(1);

struct Mov {
    std::vector<std::string> op;
    Mov& operator,(int val)
    {
        std::ostringstream os;
        os << val;
        op.push_back(os.str());
        return *this;
    }
    Mov& operator,(const Reg& reg)
    {
        op.push_back(reg.toString());
        return *this;
    }
    ~Mov()
    {
        if (op.size() != 2) throw std::runtime_error("need 2op");
        printf("mov %s, %s\n", op[0].c_str(), op[1].c_str());
    }
};

もちろん実際にやろうとすると全てのニーモニックに対して#defineしないといけないので非現実的(デストラクタで例外投げてるし).

夏のプログラミング・シンポジウムに発表参加.

今年の1月初めて参加してアットホームな感じに楽しそうで発表申し込んでみた.

テーマがビューティフルコードと私とは縁遠いかと思ったが, 「言語特有のメカニズムを駆使活用する技」や「実行の速さ」なども含んでるしまあいいかと(資料).

ところが最大200人の大規模なものになっていて, どういう聴衆をターゲットにしてよいのか最後まで迷って方針が定まらずぐだぐだな発表になってしまった. せっかくたくさんの方が聞いてくださっていたのに本当に申し訳ない.

あとテンパってたせいもあるけど全く大人げない挙動をしているところがあった. 実に恥ずかしい. 反省してます.

以下は補足など.

「C++ + x86/x64は汚い」とは言ったけど少なくとも『ビューティフルコード』の8章みたいな問題に対しては, Xbyakを使うと「ビューティフル」にかけると本当に思ってる. 少なくともC#のemit連発よりはずっと洗練されているはず. pcsx2でもそういう画像処理コード生成で使われてるようだ(ソース).

今回の発表ではその思いをちゃんと伝えられなかった. 自分の力量不足が悔しい.

「レジスタの自動割り当てや定数畳み込みなどの簡単な最適化機能はあったほうがよいのでは」という質問をよく受ける.

もちろんそういうものがあったほうがいいケースはある. ただ私が使いたいときというのはレジスタは全て直接見えて, 触れていて欲しいときなのでXbyakには入れない.

文字列処理命令のケースやフラグの処理など, 隠蔽されていてもまどろっこしいだけだと思ってる. それからもし最適化支援機能が欲しければ, そのときにあった特殊なものを用意する方がいいし楽しい. それにそんなコードを書くときに別のライブラリを頼るなんてつまらない.

O(n^2)が遅かった話.

GoogleがJavaScriptの新しいベンチマークを発表したというので@Constellationさんが自作のJavaScriptエンジンivでの評価をしていた. するとベンチマークの中のmandreel.jsがコードサイズが大きすぎて動かないらしい(C++のシンボルをデマングルしたような変数名が大量にある). 正確には止まってるのではなくコード生成処理が終わらないようだ. Safariでも落ちるしええんちゃうとも思ったけど, どこで止まってるのか見たらXbyakの中だったw

もう少しよく見ると, コード生成中にコード領域が足りなくなったときgrowMemory()という関数の中で新しくメモリを確保してコードを移動することをしていた部分だった.

/*
    allocate new memory and copy old data to the new area
*/
void growMemory()
{
    const size_t newSize = maxSize_ + inner::ALIGN_PAGE_SIZE; // (*)
    uint8 *newTop = alloc_->alloc(newSize);
    if (newTop == 0) throw ERR_CANT_ALLOC;
    for (size_t i = 0; i < size_; i++) newTop[i] = top_[i];
    alloc_->free(top_);
    top_ = newTop;
    maxSize_ = newSize;
}

私自身はコード生成中にgrowMemory()が呼ばれて領域が増えるってのは好きじゃなくて, そもそもこの機能はつい最近になるまで入れなかった.

領域が足りなくなったら(*)の部分で4KiB増やしてリトライするのだが, 今回のmandreel.jsでは数十MBのコード生成をするため, えんえんとgrowMemory()するはめになっていた. 試しに(*)の部分をmaxSize_ * 2に変更したらさくっとコード生成が終了した. アルゴリズム的にはO(n^2)がO(n)になったわけだ.

もちろんstd::vectorなどの大抵のメモリ確保戦略は足りなくなったら今までの2倍(とか1.5倍)にするというのは知っていた.

ただ実行時のコード生成はそんなばかばかメモリが必要になるものでもないし(せいぜい数十KB), 万一足りなかったとしても少しずつ増やす方が好ましいと思ってるので最初の方法が間違ってるとは思わない. でも今回の場合は, それが全体の実行時間にまでクリティカルに影響を与えていてちょっと面白かった.

GMPを使ったpaillier暗号のサンプルを作ってみた(paillier.hpp). WindowsではMPIRを使うとGMP互換ライブラリを使える. 64bitでbuildするほうがずっと高速なものが使える. サンプルコード

#include <mie/paillier.hpp>
#include <iostream>

int main()
    try
{
    mie::paillier::PrivateKey prv;
    /* 1024ビット鍵長で初期化 */
    prv.init(1024);
    const mie::paillier::PublicKey& pub = prv.getPublicKey();

    mpz_class a = 9;
    mpz_class b = 8;
    /* 暗号化前 : a, b */
    std::cout << "a=" << a << std::endl;
    std::cout << "b=" << b << std::endl;

    mpz_class ea, eb;
    pub.enc(ea, a);
    pub.enc(eb, b);
    /* 暗号化した値 : ea, eb */
    std::cout << "ea=" << ea << std::endl;
    std::cout << "eb=" << eb << std::endl;

    mpz_class c;
    mpz_class eab;
    /* 暗号化した値同士を掛けたもの */
    pub.mul(eab, ea, eb);
    prv.dec(c, eab);
    /* それを復号するともとの値の和になってる */
    std::cout << "c=" << c << std::endl;
    std::cout << "a+b=" << (a + b) << std::endl;
} catch (std::exception& e) {
    std::cerr << "err=" << e.what() << std::endl;
    return 1;
}

実行すると

a=9
b=8
ea=323543863945504360...(略)
eb=247935536850575826...(略)
c=17
a+b=17

となってEnc(a) * Enc(b) = Enc(a + b)となっていることを確認できる.

今日から晴海のホテルでラボユースの合宿. 古いホテルだなあ. トイレが1, 5, 10階にしかないので昇り降りが面倒.

Paillier暗号というのがある. Paillierさんが1999年に発表した公開鍵暗号で, 前年に岡本さん, 内山さんによるOkamoto-Uchiyama暗号というのが提案されてそれに触発されたのだと思う. で, これには加法準同型性という面白い性質がある. どういう性質かというとEnc(a), Enc(b)を数値a, bの暗号文, nを公開鍵としたとき

Enc(a) * Enc(b) mod n = Enc(a + b)

が成り立つ. もちろん秘密鍵を知らない人はa, b, a + bの値は分からない. mod nは決まってるので省略すると

Enc(a) * Enc(b) = Enc(a + b).

ある関数がこういう性質を満たすとき準同型という. 平文の加算ができるので加法性準同型と言ってる. ちなみに素のRSAも似たような性質を持っている. なぜなら

Enc(a) = a^e mod n

という形なので(mod n)を省略して書くと

Enc(a) * Enc(b) = a^e * b^e = (ab) ^ e = Enc(ab)

こちらも準同型だが, 平文の掛け算ができてるので乗法性準同型と言うことがある. ちなみに準同型の性質を持ってると, 暗号文だけから平文を改変できることを意味する. それでこの性質を持ってると単体では通常の公開鍵暗号などで一番高いとされる安全性要求は満たさない.

秘密情報をクラウドに教えることなく集計だけさせたりできるのでいろいろな応用が考えられている. 電子投票や電子現金での利用も考えられてる.

乗法性準同型の性質を持つ暗号は比較的いくつか発表されてるけど, 加法性準同型を持つ暗号はあまり知られていない. では, その両方の性質(足し算と掛け算ができる)を持つ暗号ってあるのだろうか. その性質は完全準同型(fully homomorphic)などといわれて2009年にGentryさんたちが見つけて以来活発に議論されている.

ただ今のところ鍵サイズの単位がGiBとか, 改良されてもMiBとかで実用には辛い. まあ, 将来改良されるだろう.

2日前から凄い頭痛と腹痛と嘔吐感と耳鳴りとが合併してえらい大変だった. 一日水だけで過ごしてたらなんとか治まった感じ. お腹減ってきた(という感覚が戻ってきてよかった).

昨日から気圧の変化で耳が詰まったような感覚がずっと続いていて耳鳴りも収まらない. なんかやばい気もする. 今日から夏休みで実家に戻る予定なのでパソコンせずしばらく寝てれば治るだろうか(ネットもつながらない).

てなことを言ってたら突如Linuxまわりを触ることになった. 最近のことは全然知らないので一から勉強.
とりあえずubuntuのserverとgenericの違いというのを知った.
スケジューラとpreemptionとtimer割り込みの値が違うそうな. 今いじってるデバイスのスケジュールがどうなってるかは, たとえば/dev/sdbなら

% cat /sys/block/sdb/queue/scheduler

でわかる. スケジューラのタイプをdeadlineに変更するには

% sudo sh -c "echo deadline > /sys/block/sdb/queue/scheduler"

で, deadlineとcfqでとあるアプリの挙動が違うってのはやっぱりバグなんだろうなあ.

ここしばらくCompound File Binary File Format やらOffice Document Cryptography Structure Specificationを眺めながらPowerPointファイルを目grepしたりバイナリエディタで切り貼りしたり, ちょっとしたツールを作ったり.
こういうのはパズルっぽくて嫌いじゃなかったりする. レガシーなMSの技術ベッタリなのがあれだけど.

opensslのHMACコマンドではまった話で, 結局hex入力できるオプションをつけみたよとMLに投げてみたら, 開発者の方に

>openssl dgst -sha1 -mac HMAC -macopt hexkey:aabbcc <input-file>

というオプションでできると言われた(ちょっと恥ずかしい). それにしても凄いわかりにくいオプションだ. 0.98のやつにはなかったので1.0系からついたのかな.

気がついたら7月が終わってた. 冷凍庫の奥にあった2年ぐらい前に買った少し大きめのアイスクリームを食べてみた. アイスクリームは賞味期限が無いので大丈夫だろうと思ったけど結構霜がついていた. それをどけて食べてみると何故か冷たいと感じない. ポサポサというか変な感触. 水分が飛んでしまったのかなあ.

憂鬱な午後のひととき