憂鬱な午後のひととき

4月17日_

iPhoneでWebAssembly

前回iOS 11.2.2から11.2.5にupdateしたらWebAssemblyが使えなくなったので今回は様子見していたがiOS 11.3は大丈夫らしいのでupdate.

ID baed encryption demoが正常動作した.

4月16日_

『気ままに漢詩キブン』(足立幸代 三上英司)

おもろかった. 著者自身による独特なイラストと斬新な翻案. 漢詩で「ドタキャン」や「ツンデレ」が出てくるとは思わなかった.

4月14日_

wasmの読み込みパス

今まではModule.wasmBinaryFileに絶対パスを指定していたのだけど, いつのまにか(or 大分前から?)それではnpm installしたときに動かなくなっていた.

コードとドキュメントとを読み直して

const Module = {
  locateFile: baseName => { return path.join(__dirname, baseName) }
}

としたら正しく動くようになった. それからnode testでは動くのにnodeしてからrequireするとrandomgeneratorでエラーになっていた.

遅延ロードされてるのか何かよく分からないが最初に明示的に

const crypto = require('crypto')
crypto.getRandomValues = crypto.randomFillSync

したら動くようになった.

4月13日_

ビット演算クイズ回答

問題はビット演算クイズ参照.
昔, 私が試行錯誤して見つけた方法を振り返る.

int calc(int a, int b, int s)
{
    const int Q = 1 << s, Q2 = Q * 2, Q3 = Q * 3;
    assert(0 <= s && s <= 16 && && 0 <= b && b < a && a < Q * 4);
    int n = 0;
    for (;;) {
        if (a < Q2) {
            n = n * 2;
        } else if (b >= Q2) {
            n = n * 2 + 1;
            b -= Q2;
            a -= Q2;
        } else if (b >= Q && a < Q3) {
            b -= Q;
            a -= Q;
        } else {
            break;
        }
        b = b * 2;
        a = a * 2 + 1;
    }
    return n;
}

まず関数の形を理解する. sが決まると(a, b)は0 <= b < a < Q * 4の三角形Dの中を動く.
ifの中を見ると

その後(a, b)は(a * 2 + 1, b * 2)に移動する. そうやってループを抜けるまでDの中を移動した回数を返す.
(a, b)の動き

テーブル引きをしようと思ってもテーブルサイズが大きそうだ.

次に具体的な数値を眺めてみる.
出力の一部

値は結構小さい. 三角形の斜辺近くに比較的大きな値が並んでいる感じがする. 斜辺の値(a, b = a-1)を取り出して並べてみよう.

a  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
n  0  0  1  0  2  1  3  0  4  2  5  1  6  3  7  0  8  4  9  2

奇数のところは値が半分. 2べきのところは0になっている. それ以外の偶数は?
何ビットシフト(s)したらnになるのかみてみる.

a  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
s  1  2  1  3  1  2  1  4  1  2  1  3  1  2  1  5  1  2  1  3

なんとなく規則性がありそうな, 無いような.
aを2進数表記して下から0が続く個数zを数えてみる.

a  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
      0  1  0  0  1  1  0  0  0  0  1  1  1  1  0  0  0  0  0
            0  1  0  1  0  0  1  1  0  0  1  1  0  0  0  0  1
                        0  1  0  1  0  1  0  1  0  0  1  1  0
                                                0  1  0  1  0

z  0  1  0  2  0  1  0  3  0  1  0  2  0  1  0  4  0  1  0  2

s = z + 1っぽい. つまりaの下から0が続く個数 + 1だけ右シフトするとn.

とするとcalc(a, a - 1) = a >> (bsf(a) + 1).

b = a - 1以外のbではどうだろう.
頑張って眺めてみるとa ^ bの上からみて初めて1になる場所(bsr)だけずらせばよいようだ.

a >> (bsr(a ^ b) + 1).

しかし, 斜辺がbsfでそれ以外がbsrだと扱いづらい.

bsfとbsrの関係
x ^ (x - 1)が何を意味するかを思い出す. xを2進数展開して下から何個か0が続き初めて1が立ち, そのあと?な状態として表す. xは一般的にそのように書ける(連続する0が0個のときを含める).

x      = ? ? ? ? 1 0 0 ... 0
x - 1  = ? ? ? ? 0 1 1 ... 1
x^(x-1)= 0 0 0 0 1 1 1 ... 1

xの下からみて初めて1になる場所bsf(x)はx^(x-1)の上からみて初めて1になる場所bsrに等しい. つまり

bsr(x ^ (x - 1)) = bsf(x).

斜辺はb = a - 1なのでbsf(a) = bsr(a ^ (a - 1)) = bsr(a ^ b)と同じ形になった.
結局

int calc2(int a, int b, int s)
{
    return a >> (bsr(a ^ b) + 1);
}

という形になった(実際にこれが元の関数に一致する検証は省略 : 追記 @shinhさんによるロジカルな回答 ビット演算クイズを解いた時の話). 興味深い点が二つ.

  1. calcはsに依らない
  2. a >> (bsr(a ^ b) + 1) == b >> (bsr(a ^ b) + 1).

さて, ここまで簡単になるとSIMD化したくなる. しかしbsrのSIMD命令は無いのでどうするか.

bsr(x)は上からみて初めて1が立つ場所なのでceil(log2(x))に等しい.

xの浮動小数点数表記はfを1以上2未満の小数, eを整数としてx = f * 2eとかけるので 整数xをfloatに変換して指数部を取り出せばよい(codec-calc-ans.cpp).

static inline int bsr(int x)
{
    assert(x > 0);
    union {
        int i;
        float f;
    } ui;
    ui.f = (float)x;
    return (ui.i >> 23) - 127;
}

これならcvtpi2psを使うことで容易にSIMD化できる.

4月10日_

ビット演算クイズ

codec-calc.cpp のcalc関数はassert()が成り立つ条件下で分岐のない形に書き換えられる. テーブル参照は使わない.

もともとは, 大昔とあるコーデックの処理でこの関数相当の処理が70%近く時間を占めていたので最適化の必要があった. いろいろ考えてうまい方法が見つけて喜んだのであった.

と言っていたら@shinhさんが早速答えていた.すごいなあ.

4月9日_

ASIA CCS 2018採択ありがたい

"Efficient Two-level Homomorphic Encryption in Prime-order Bilinear Groups and A Fast Implementation in WebAssembly"

もともとはFreeman方式を実装したくて論文を読んだのだけど抽象的に書かれていて肝心なアルゴリズムがよく分からない. 自分でアルゴリズムを試行錯誤して実装したのを説明していたら共著者の一人の坂井さんに, 「ElGamal暗号を使ったら簡単になるのでは」と言われて紙と鉛筆で計算し直したらうまくいったのであった.

できあがってみればとてもシンプルなので気に入ってる. もっと昔に思いついていたらもっとよかったのだけど, それは無い物ねだり.

4月8日_

BLS signature for Node.js

というわけでこちらもBLS12-381に対応させた. ただまだいろいろ実装してないアルゴリズムがある. 論文が分散していて参照するのが大変. 一つずつやっていこう.

署名に使うならBN381のほうがよいのかな.

4月5日_

BLS12-381 on browser

ID beased encryption demoがBLS12-381曲線に対応した. うれしい. しかしペアリングだけ(BN381より)速くなっても群の巾乗算やmapToPointも速くならないとアプリによっては遅くなりそう.

4月4日_

Re: objdumpのバグ?

すごいスピードで修正されてびっくりしてる.

4月3日_

objdumpのバグ?

AT&T記法はよく見るmovやaddぐらいならよいけどFPUまわりや3オペランドやAVXの命令長指定サフィックスとか辛い(というか私には無理)と思いながら実験していて見つけた.

% objdump -M x86-64 -D -b binary -m i386 vcvtpd2dq.bin

vcvtpd2dq.bin:     file format binary

Disassembly of section .data:

00000000 <.data>:
   0:   67 c5 fb e6 40 20       vcvtpd2dqx 0x20(%eax),%xmm0      ; (X)
   6:   67 c5 ff e6 40 20       vcvtpd2dqy 0x20(%eax),%xmm0      ; (Y)
   c:   67 62 f1 ff 18 e6 40    vcvtpd2dq 0x20(%eax){1to2},%xmm0 ; (Z)
  13:   04
  14:   67 c5 fb e6 40 20       vcvtpd2dq 0x20(%eax),%xmm0       ; (X')
  1a:   67 c5 ff e6 40 20       vcvtpd2dq 0x20(%eax),%xmm0       ; (Y')

同じバイト列に対する逆アセンブル結果が(X)と(X'), (Y)と(Y')とで異なっている.

vcvtpd2dqのサフィックス(xやy)があったり無かったりしたので, あれ?と思って調べたらブロードキャスト命令が途中に入るとおかしくなるようだ.

逆アセンブラが状態を持つというのはあまり想像できないけど, 滅多に使われなさそうなブロードキャストモードで何か初期化すべき状態が残ってしまってるのだろうか. 面白いバグだな.

以前見つけたYASMのオブジェファイルの出力とリストファイルの出力のバイト列が異なっていたバグもあれだったけど.

4月2日_

BN曲線とBLS12曲線

それぞれ別クラスとして実装していたのだけど, 使う側からすると切り替えるのが面倒. KSSやBLS24などはどうするという問題はさておき, とりあえず統一して使えるようにするか.

4月1日_

branchScope

論文読みながらのメモ書き. 実装で推測するところでPrimeがTTTとNNNのどちらかしか無いのは仮定してよいのか, あるいはそのように誘導するのか, probe_arrayでTTしかしないのか, NNはやらなくてよいのかといった一番肝心な部分がまだちゃんと分かってない.

が, 発動条件がそうとう厳しいということは理解できたのでまあいいか.


御意見は光成滋生<herumi@nifty.com>までお願いします