melancholic afternoon

PowerPointの隠し文字表示

Twitterで作ってみたよと書いたら300以上のリツイートがあった. 興味持ってる人が多いのね. ちゃんと実装することを考えてみるか.

行き先

http://herumi.in.coocan.jpに移動した. inじゃなくてonだとfacebookにブロックされてるらしい. なんじゃそりゃ. ここも勝手にそうなってしまうのだろうか. 結構前かららしいけどnifty直す気ないのか.

ホームページ移動

niftyのhomapgeが無くなるので移動. 16年以上使っていたのか. webサービスとしては凄まじく長かったな.

ずっとプログラム開発やってこれてありがたい.

情報幾何学の基礎輪読会

4章最後までと5章最初を担当.

お昼はC++WG委員会で移動が面倒だった.

未初期化変数の利用は未定義か

int a;
int b = a; // ***

というコードで***は未定義だったけと尋ねたらyesと教えていただいた.

n4604の8.6の12に

If an indeterminate value is produced by an evaluation, the behavior is undefined except in the following cases:...

とあってunsigned char以外の未初期化な値を見るのはだめなようだ.

unsigned char c;
unsigned char d = c; // OK, d has an indeterminate value
int e = d; // undefined behavior

C++11からC++14に変わるときにこの例が入っていた. unsigned charだけ特別扱いなのは最適化のためだそうな(Uninitialized unsigned char values). どうもありがとうございました.

mie_string

SSE4.2を使うやりかた, 何度か書いてるけどやはりintrinsicなものとasmで書いたものがあると(自分にとって)便利なので用意した.

ループ処理はどんなフラグをつかうかいろいろ試したところ,

.lp:
    pcmpestri xmm1, [rdi], mode
    jna .exitLoop
    add rdi, 16
    sub rdx, 16
    jnz .lp

mie_string_x64.asmが一番よさそうだという結論になった. 5clk程度で回るようだ. つまり16byte/5clkで1clkあたり3byte程度の処理.

Power Pointの隠れ文字検出

Excelなどで作ったグラフをPower Pointに張り付けるとグラフに見える情報以外のデータも内部的に張り付けられてしまうことがある. それが制作者の意図しないものだと問題だなというわけで, 隠れ文字検出をするツールを試作してみた.

その紹介ブログ. ツール自体はまだ非公開.

『情報幾何学の基礎』

5章の準備. いよいよ双対多様体の具体的な例がでてくるようだ. 幾何学からいきなり組み合わせ論的な話に移った.

EC/Fp2の点の圧縮表現

Fp2の平方根を実装したのでEC/Fp2もy座標を1ビットで表現できるようになった.

Fp2の平方根

まだ実装していなかった.

x = a + bi, i² = -1とするとx² = (a² - b²) + 2abi. c = a² - b², d = 2ab, A = a², B = b²とすると c = A - B, d² = 4AB. よって

c² + d² = (A + B)².

そこでまずc² + d²を計算して平方根をもとめてからc, dを求めてa, bをだせばよい(Fp2::squareRoot).

Rogue Key Attacks

というものがあるらしい. 分散署名において検証鍵を変更して渡すことで自由に署名をつけられるようにする.

これに対抗するには検証鍵pkとpkに自分で署名したもののペアを渡すことでOK? 本当?

VSS

bls署名にFeldmanのVSS(Verifiable secret sharing)をつけた. といっても単に秘密鍵s_iに対するs_iQを公開して正しい公開鍵かを確認するだけ.

よく考えたら秘密分散とVSSは公開するものがほとんど同じだ. (Q, c₀Q, ..., c_k-1Q)をマスター公開鍵としてidを持つユーザが f(id)Qを計算して自分の公開鍵とすればよい. f(x) = c₀ x + ... + c_k-1 x^k-1.

BLS署名

欲しいという人がいたので実装してみた. 楕円曲線のP ∈ G1, Q ∈ G2を固定する. sが秘密鍵でsQが公開鍵. Hash : {文字列} → G1を使ってメッセージmの署名をs Hash(m)とする. e(s Hash(m), Q) = e(Hash(m), sQ)で確認する.

mclを使って実装したので簡単.

実家でずっと実装していた. ネットワークにつながらないと余計な時間を使わず集中できてよい.

『左京区七夕通東入ル』(瀧羽麻子)

数学科で卒論は無かったよなあと思っていたらそういうオチだった. ちょっとうけた.

夏休み

実家に戻る. しばらくメールなどは読めません.

gccの-Wallと-Wextraの関係

何も考えずいつも両方つけていたのだけど「-Wextraは-Wallを含んでるの?」という質問があったので調べてみた. -Wallでしかない警告や-Wextraでしかない警告があるのは当然として, 両方つけないとでない警告があるというのは初めて知った.

% cat t.c
void f(int x) { }
% gcc -c t.c
% gcc -c -Wall t.c
% gcc -c -Wextra t.c
% gcc -c -Wall -Wextra t.c
t.c: In function 'f':
t.c:1:12: warning: unused parameter 'x' [-Wunused-parameter]
 void f(int x) { }
            ^

ちなみにclangだと-Wextraのみで出た. そしてC/C++/Objective-C compiler warning flags collection and parsersを見てclangには-Weverythingというオプションがあることを知った.

% clang -c -Weverything t.c
t.c:1:12: warning: unused parameter 'x' [-Wunused-parameter]
void f(int x) { }
           ^
t.c:1:6: warning: no previous prototype for function 'f' [-Wmissing-prototypes]
void f(int x) { }
     ^
2 warnings generated.

憂鬱な午後のひととき