憂鬱な午後のひととき

新聞の報道の解釈

一晩中泣き明かした30歳若手女性研究者と書く我が国にはゴシップ新聞しかないらしい

朝日新聞は割烹着姿の小保方博士をトップに置き、「３０歳の若き女性研究者」と紹介しています。また、博士なのにも関わらず「小保方さん」と呼んでいます。発見そのものに関する詳しい説明はありません。

今日のテレビ欄, リケジョやかっぽう着のタイトルが多くてややげんなりしたけれども(中身は見てない), この人の引用も作為的. 「日本のメディアはくだらない記事しかかけない」という思い込み, あるいは結論ありきなんじゃないかな.

実際のところ, 1/30の朝日新聞の1面は技術的な解説(ここでは小保方ユニットリーダーという呼称), 2面ではES細胞やiPS細胞との比較, 今後の課題などが書かれていた. 引用にある記事は社会面ですね.

他の新聞がどうかは調べてないし, 今回のに限らず差別的な表現が見え隠れするのは否定しないけど, 当日の報道はそんなにいうほど酷いものではなかったと思う.

mapかtr1/unordered_mapかunordered_mapかの判別

Xbyakではジャンプ先のラベルを扱うところでstd::mapを使っていたのだけど, 以前@Constellationさんが高速化のためにunordered_mapを使えるなら使って欲しいという依頼があって対応していた.

今どき, C++11対応してないなんて(もっと酷い人はC++14対応してないなんて)とか言う人もいるかもしれないけど, 実際にはそんな割り切りはそうそうできるものでもないし, 個人的にはまだしばらくはしたくもない. 規格のためにコードを書いてるわけじゃないしね.

まあ, それはともかく当初は_MSC_VERと__cplusplusぐらいしか見てなかったのだけど, Clangの一部のモードでは新しくてもgcc 4.2と名乗ることがあるらしくてややこしい判別のpatchをもらった(diff).

対応する環境をどこまで広げるかというのは難しい判断だけど, こういうのが増えて自分がメンテできなくなってくるころが判断の目安の一つかなと思う.

『失踪日記』(吾妻ひでお)

漫画を描いてる途中で原稿を落として失踪. 悲惨な状況を明るくさっぱり書くのがすごい. ホームレスになって食べ物に困る状況でも煙草は吸いたくなるものなんだなあ. 私はお酒も煙草も飲まないのでわからない.

アル中で入院するところは『今夜、すベてのバーで』(中島らも)と一緒だ(久しぶりに読み返したくなった). 奥さん(やその周辺の人)がどんなに大変だったか.

ところで今日初めて酷い勘違いに気づいたのだが, 吾妻ひでおの奥さんって新井素子と思い込んでいた.なんでだろう.

SCIS2014の4日目

4D1-3 多項式時間・領域秘密正規表現照合アルゴリズム

正規表現をNFAで秘匿したまま処理する. どこを探しているかばれないようにするため常に全部チェックするのが重たい. 完全準同型暗号が必要なので乗算を毎回クライアントと通信が発生するのが痛い. がとてもおもしろい.

4D2-2 インターネット環境レスポンス1秒の統計処理を目指した, 秘密計算基数ソートの改良

暗号化したまま統計処理を行いたい. まずはソートをしたい. 準同型暗号は重たいので秘密分散を使う. 秘密分散ベースの手法は1000件のソートに1秒ぐらいだった. 新しい手法により14万/秒まで性能向上させた. 基数ソートで順序を取得する部分の巧妙なロジックがすごい. 分岐をなくして高速化する手法に雰囲気がよく似てる.

4D2-3 秘密計算一括写像計算の効率化

こちらも同じモチベーション. 複数のテーブル引き要求をまとめて行うことで高速化する. やはり巧妙なトリックがすごい.

帰りの飛行機はとても小さいやつだった.

SCIS2014の3日目

大鳥居からホテル正面入り口まで本当に5分でいけるかもっぺんきちんと測定してみた. 鳥居から軽くスタートして階段が始まるまでは約1分. 階段を登り切ったところで4分30秒ぐらい. そこからホテルまで40秒ちょっと. 結構しんどい. 昨日は階段部分だけを5分ぐらいで登ったようだ.

朝御飯を食べていたらちょうど目の前で桜島の稜線から日の出が見えた. 実際に見るのは初めてかも. まじまじと見てると太陽の動きって速い.

「暗号したまま○○する」が大はやり. 検索可能暗号関連の発表件数がとても多い. だが正直なところ, 通常の検索に比べてまだ(とても)²遅いし, 検索可能暗号で守ろうとする情報が何なのかピンとこない. 当分は医療などのセンシティブなところで要件を考える感じなのかなあ.

3F2-4 Private Set Intersectionに対する委託可能な方式

PSIとは集合Aを持っている人と, 集合Bを持っている人が, 互いにもってる情報を出さずにA ∩ Bを求めること. 去年, ブルームフィルタを使った方法が提案されたらしい. その紹介の話も面白かったが, それを委託可能なものにする提案も面白かった. プレゼンの巾乗のrをどう扱うのか分かりにくかったが, 本当はいろいろ細工をするらしい.

3B5-1 CRYPTREC暗号技術評価委員会活動報告

電子政府に推奨される暗号技術のリストは民間の会社はどう受け取るべきなのか. 質疑応答が興味深かった.

セッションが朝から晩まであって新しいことをたくさん聞いてると頭がパンクした. 帰ったらきちんと勉強しよう.

何人かの方から『PRML本』(pdf)売れてましたねと言われたけど, あれ私は出版にはかかわってないのでお金はやってこないんですよね(というと必ず驚かれる).

SCIS2014の2日目

朝5時頃起きる. 城山自然遊歩道のとなりに急な石段があるというのでどんなものか行ってみた. まだ夜が明けてないので暗くて怖いが無事に降りれた. しばらく天文館あたりをジョギングしつつうろついていたら少し明るくなってきたので戻って登ってみる. 大鳥居のところからホテルまで5分ちょい. 言われてるほどではなかった. 大学のときに一気に駆け上がろうとした奈良の室生寺(700段)は流石に息切れしたもんだが.

1日目残り

1D3-4 準同型暗号を用いた秘匿生体認証

指紋から特徴ベクトルを取り出す場合, 同じ人の指紋であっても常に完全に同じものがとれるとは限らない. ビットベクトルの差のハミング重みが多少あっても許可しないといけない. 提案されるRing-LWEベースの手法は加法は複数回と乗算は1回までは可能な準同型暗号である. 乗算のたたみ込みの計算が一度でできる程度に係数を大きくした(?)ところが特徴らしい.
多項式の乗算にFFTを用いた高速な実装をして実際にデモをされていた.
最後, 求めたハミング重みを誰が復号して同一性を確認するのか分からなかった(クライアントでしかできないはずだがクライアントでするなら意味がない).

1D3-5 準同型暗号を用いた秘匿検索

他の秘匿検索は, 予めキーワードを決めておくかインデックスの更新をする手法が多い. 1D3-4と同じ手法を用いて対象データと検索キーワードとのハミング距離を1文字ずつずらしながら行うことで任意の文字列マッチングを実現した.
こちらの場合はクライアント側で復号するので1D3-4の問題は無さそうだ. ただサーバからクライアントに返す暗号化されたデータ量がかなり巨大になりそうな気が. うーむ.

2日目. 朝8時40分開始. セッションが多いのでしんどい.

2E1-1 固定された係数を持つペアリングフレンドリ曲線

ペアリングのためのパラメータを決めるときに従来の順序と異なる順序で行うことで, 楕円曲線の定義方程式の係数を2巾になるように選択できる. これにより少し演算コストを下げることができる.

2E1-2 Supersingular な楕円曲線における Weil ペアリングの効率化

去年, 標数が2や3の体上の超特異な楕円曲線上のペアリング暗号は予想されていたものよりずっと弱いことが分かった. そのため対称ペアリングが必要な場合は大きな標数上での超特異な楕円曲線上で考える必要がある. その曲線に対して効率のよい手法を提案する.
# なんと大昔(2003年頃)IPA未踏で実装してたペアリングに戻ってきた!

2E1-3 上位ビットを固定した合成数位数の効率的なペアリング

通常, 構成されるペアリングは素数位数だが合成位数だとまた違ったプロトコルを構成できることが知られている. ただ合成位数場合はとても処理が重くなる. 合成数のハミング重みが小さくなるように値をうまく選ぶことで19%の高速化を達成した.

2E1-4 タイプ1の双線形写像群の暗号方式からタイプ3への変換アルゴリズムの実装

対称ペアリングを用いて構成される暗号プロトコルを非対称ペアリングを用いて実現する場合, ハッシュがあるとできないし, ない場合でもパラメータの二重化が必要になる. プロトコルに現れるパラメータの依存関係をグラフで表現し, 二重化を最小になるパターンを探すことで効率のよい変換を導出する. またそのためのツールを実装した. それにより従来できないと思われていたVRL Group署名を変換できることが分かった.
面白いな.

ソフトウェア保護関係. 当然のように自己書き換えや命令の一部を変更するなどの手法がいっぱい. 難読化手法の提案とそれを回避する攻撃側の手法の提案. こちらの世界も面白そうだな.

2D2-1 N-gramモデルを用いたソフトウェア保護機構の不自然さ評価

普通のコードのある命令の次に続く命令の確率を求め, 与えられたコードの生成確率をN-gramモデルを使って数値化する. それによりもっともらしいコードか不自然な(自己書換えなどの怪しいことをやってる)コードかを判定する.

SCIS2014の1日目

羽田空港に向かうために東横線に乗ったところでトラブルのため停止というアナウンスでちょっと焦る. 幸い5, 6分で動いたので無事到着. 飛行機は風が強いため予定と違う行路をとったらしいがこちらも無事到着.

SCIS2014のプログラム. 初めて座長して緊張した. 適当なメモ.

1C1-3 LLL格子基底が最短ベクトルを与える確率について

LLL格子基底の中で, その第一ベクトルが最短であるもの(sLLL)がどれぐらいあるのかという基本的な問いに対して考察する. LLL全体をsLLL全体のユニモジュラー行列での変換の有限個の和でかけることを示し, 少なくとも0ではないという結果をえた. 数学的には面白そうだと思ったのだけど, 定義される確率がどのぐらい妥当なのかという質問があった.

1C2-1 線形代数ステップにおけるLanczos法の実装実験

素因数分解や離散対数問題を解く際に, 大規模疎行列Aに対してAx = 0(mod p)となる0でないxを求める必要がある. それの高速な実装実験と各種手法の効果についての解説. プリフェッチ命令を使ってもなかなか速くならないという話を伺った. 私はプリフェッチ命令を使ってよかったことは殆どないなあ.

1C2-2 奇標数の有限体上の多変数連立2次方程式の求解アルゴリズムの改良について

有限体上の多変数連立2次方程式を解く問題は一般的にはNP困難だが特定の条件下では多項式時間で解ける. そのアルゴリズムの改良を行う. 奇標数上である数xの平方根が無ければ-xでリトライするというアイデアがシンプルだけどよい感じ.

1C2-3 既約因子の次数に制限がある多項式の因数分解について

有限体上の1変数多項式の因数分解アルゴリズムの改良. 超楕円曲線の指数の計算だと1万次以上がいるらしい. 因子の次数に制約を置く事で既存手法の改良とその実装実験. スライドが左右二つに分かれて一つ前のものが常に参照できるようになっていた.

1C2-4 2べき剰余環上のチェビシェフ多項式から得られる系列の周期

Z/2^nZ上でChebyshev多項式を繰り返し適用する事によりえられる数列の周期が2巾になることを示す. ちょっとテストプログラムを書いてみてみるとその系列って下位ビットは全然変化しないんだなあ.

1A3-1 関数型暗号に適応可能なマルチペアリングの高速化手法

関数型暗号ではペアリングを多数使う事になるので高速化したい要求が強い. 複数のペアリングの片方の点が固定である事を利用して事前計算をうまくすることで本体の処理を軽減する.

1A3-2 SSE-2に基づく動的な検索可能暗号システムの提案

検索可能暗号とは, 暗号化されたファイルをサーバに置き, 検索キーワードも暗号化したままサーバ側が何を検索しているのか分からないまま検索結果を返す暗号. ここではキーワードとファイルの対応関係を記述したインデックスを構築する手法に関するもの. 既存方法ではインデックスを変更できないか, できても大きなインデックスになってしまっていた. キーワードとファイルの対応情報を増やす事でそれを軽減する.

1D3-3 ハミング重みと基本対称式、および完全準同型暗号への応用

平文空間が1bitである現在の完全準同型暗号の平文空間をZ/QZに拡張する. その際, ブール変数のハミング重みを基本対称式で表現したいたところを, Z/QZのハミング重みに対しても同様の事ができることを示した.

疲れた.

明日からSCIS2014

参加させてもらえてありがたい. しっかり勉強しよう.
鹿児島に三菱東京UFJのATMはないのか. 空港でお金を下ろしておかないといかんな.

rep ret

昨日のrep nopがpauseになるのとはちょっと違うけど, コンパイラの生成コードでretにもrepがつくことがある. 最初見たときはなんだこれとびっくりする(Intelのマニュアルには載ってないし)が, これは昔のAMDのCPUではretよりもrep retのほうがよかったかららしい. CPU family 16h(15hから?)ではそんなことしなくてもいいようだ.

pause命令のintrinsic関数

spin lockなどのbusy loopではメモリのアクセス順序やパイプラインのフラッシュのためにCPUのリソースを使う. pause命令はそういう状況であることをCPUに教えてCPUの負荷や消費電力を下げるための命令で, Pentium 4で搭載された.

この命令のバイトコードは0xf3 0x90でこれはちょっと面白い. 0xf3はrepプレフィクスで0x90はnop. Pentium 4以前のCPUではこのプレフィクスは無視されて単なるnopになる. つまりPentium 4以降であることをチェックせずに使っても害は特にない(ということがIntelのマニュアルに明記されている).

CPU判別して処理ルーチンを変える必要がないのでありがたかった. spin lockなんてちょっとずつ違うものがあちこちにあるので, いちいちコードを分けていては大変. だからバイトコードをうまいこと選んだんじゃないかと想像する.

さてこの命令のintrinsic関数は_mm_pause()だ. gcc/clangならx86intrin.hを, VCならintrin.hをincludeすれば使える. __builtin_ia32_pause()というgccの組み込み命令もあるけどgcc 4.7以降で, clang 3.4は未サポートなので_mm_pause()の方がよいだろう.

前述のように_mm_pause()命令は全てのx86/x64 CPUで動作するのだけどgccは何故か__SSE__を定義してないと_mm_pause()が使えなくしていた. SSEはPentium 3から使えてるのでなんか変な気がする. Debianのi386パッケージは__SSE__を定義してないようで(何故?), そこでpauseを使おうとするとエラーになってしまった(FTBFS on i386: '_mm_pause' was not declared in this scope. Pentium 4登場時期ならいざ知らず, こんな現象が今頃発覚するのは不思議だな.

データ構造と情報検索と言語処理勉強会 #DSIRNLP 5に参加

ゆるゆるな感じかと思ったら初っぱなら, がちな話が続いて目が覚めた. 実用的になるのかまだ半信半疑だけど@iwiwiさんのCache-Obliviousなデータ構造の話が面白かった(Cache-Oblivious データ構造入門).

『時砂の王』(小川一水)

突然襲ってきた地球外生命体からの攻撃に対処するため過去にメッセンジャー(人型のロボットみたいなの)を送って戦う. 過去に介入することで歴史が変わる. よくある設定だけどメッセンジャーの目的が自分が作られた世界を守るのではないのがちょっと違う.

繰り返し戦い連戦連敗でどんどん過去に遡る. だんだん戦力に使えるリソースも足りなくなる. テンポよくて面白い. ただ, タイムトラベルの連続としては『タイム・リープ―あしたはきのう』(高畑 京一郎)のほうが結末がすっきりしてたなあ.

x64でアライメントエラー, それからpadddとvpadddの違い

会社で他の人が書いたとあるコードが落ちることがあったので原因を探るためにコードを最小化したら次のようなものだった.

#include <stdio.h>
#include <stdint.h>
#include <memory.h>

uint32_t checksum(const void *data, size_t size, uint32_t csum)
{
    const char *p = reinterpret_cast<const char *>(data);
    while (sizeof(uint32_t) <= size) {
        csum += *reinterpret_cast<const uint32_t*>(p);
        size -= sizeof(uint32_t);
        p += sizeof(uint32_t);
    }
    if (0 < size) {
        uint32_t padding = 0;
        ::memcpy(&padding, p, size);
        csum += padding;
    }
    return csum;
}

int main()
{
    const int n = 128;
    char buf[n] = {};
    printf("adr=%p\n", buf + 1);
    uint32_t v = checksum(buf + 1, n - 1, 0);
    printf("v=%x\n", v);
}

このコードはg++(4.6～4.8)でarch=core2としてコンパイルすると落ちる.

>g++ t.cpp -Ofast -march=core2 && ./a.out
adr=0x7fffffffe181

Program received signal SIGSEGV, Segmentation fault.
0x0000000000400793 in checksum(void const*, unsigned long, unsigned int) ()
1: x/i $pc
=> 0x400793 <checksum(void const*, unsigned long, unsigned int)+243>:   paddd  xmm0,XMMWORD PTR [r9]
(gdb) p/x $r9
$3 = 0x7fffffffe181

g++は上記コードのループを自動ベクトル化するときにuint32_t * 4のデータと想定して最適化する(clang 3.4やVC2013ではこの最適化は行われないようだ). このため入力データが16byteアライメントされていないと, アライメントが必要なpadddで落ちる.
# 注意 : このコードが悪いのであってgccのバグではない.

Intel CPUは昔からintなどの変数はアライメントされていなくてもアクセスにちょっと遅くなるだけで落ちることは無かったが, このような最適化が入ってくるなら安易なキャストは今後よりいっそう気をつけないといけない.

これを避けるにはpをuint32_t*にキャストするのではなくmemcpyを使えばよい.

    while (sizeof(uint32_t) <= size) {
        uint32_t v;
        ::memcpy(&v, p, sizeof(v));
        csum += v;
        size -= sizeof(uint32_t);
        p += sizeof(uint32_t);
    }

memcpyを使えばすごく遅くなりそうに思えるがこの場合もベクトル化される(たいしたものだ). この場合一番内側のベクトル化されたコードはmovdquが使われる.

   // キャストバージョン
.L13:
    add rcx, 1
    paddd   xmm0, XMMWORD PTR [r9] ; 要アライメント
    add r9, 16
    cmp r11, rcx
    ja  .L13

  // memcpyバージョン
.L9:
    mov r9, rax
    add rax, 1
    sal r9, 4
    cmp rdx, rax
    movdqu  xmm1, XMMWORD PTR [rdi+r9] ; アライメント不要
    paddd   xmm0, xmm1
    ja  .L9

ところで元のコードは-march=core2ではなく-march=avxにするとmemcpyを使わなくても動く.

.L13:
  // キャストバージョン(avx版)
    add rcx, 1
    vpaddd  xmm0, xmm0, XMMWORD PTR [r9]
    add r9, 16
    cmp r11, rcx
    ja  .L13

最初, たまたまr9のアドレスがアライメントされて動くようになったのかと思っていたが, そうではなかった.

padddと違ってvpaddd reg, reg, memはmemがアライメントされていなくても動くのだった. 手元で実験すると確かに動いてる. えー, それは知らなかった. どこかに書いてあるのだろうか.

IntelのArchitectures Software Developer's Manualを見直す. paddd, vpadddの例外パターンはType 4. で, Type 4は48ページのException class descriptionに書いてある.

するとLegacy SSEはalignedだけどAVXは16/32 byte not explicitlyとある.

AVXでアライメントが必要なType 1のException Classはvmovapdなどの明示的なやつとmovntdqなどのキャッシュ制御系のmovだけだった. それ以外の普通の演算系はアライメントは不要なようだ. 単に3オペランドになっただけど違ったんだ.