憂鬱な午後のひととき

WASMでi128

以前試したときはエラーになっていたけど最新版では使えるようになっていた. まだ直接mclをやろうとしてもエラーになるのだけど一部は確認できた.

define void @add(i128* %pz, i128* %px, i128* %py)
{
  %x = load i128, i128* %px
  %y = load i128, i128* %py

  %z = add i128 %x, %x
  store i128 %z, i128* %pz
  ret void
}
// emcc -s WASM=1 -O3 -s "MODULARIZE=2" -s "EXPORTED_FUNCTIONS=['_add']"
// wasm-objdump -dx a.out.wasm
get_local 1
i64.load 3 8
set_local 3
get_local 0
get_local 1
i64.load 3 0
tee_local 4
get_local 4
i64.add
tee_local 5
i64.store 3 0
get_local 0
get_local 3
get_local 3
i64.add
get_local 5
get_local 4
i64.lt_u
i64.extend_u/i32
i64.add
i64.store 3 8
end

ああ, 64bit乗算はやっぱり駄目だった.

define i128 @mul(i64 %x, i64 %y) {
    %x0 = zext i64 %x to i128
    %y0 = zext i64 %y to i128
    %z = mul i128 %x0, %y0
    ret i128 %z
}

Unsupported:   %z = mul i128 %x0, %y0
LLVM ERROR: Binary operator type not yet supported
for integer types larger than 64 bits

WASMのCからJSを呼び出す

大きく二つの方法があるようだ.

一つ目はemscripten.hをincludeしてEM_ASMを使う(INTの戻り値が欲しいならEM_ASM_INT, doubleならEM_ASM_DOUBLE). このマクロの実体はemscripten_asm_const_int関数. 第一引数にJSのコードの文字列を渡す. 後ろの引数はその文字列に渡す変数.

たとえばx + yを返すJSをCの中で記述するには

#include <emscripten.h>
int callJS(int x, int y)
{
    return EM_ASM_INT((return $0 + $1), x, y);
}

とする. JSの中で引数は$0, $1, ...で参照する.

複雑なコードを書くとエラーになったのでWASMインスタンスmodに実際処理したい関数を記述し, EM_ASMの中でそれを呼ぶ方が楽かもしれない.

// JS側
mod.callAdd1 = function(x, y) {
    return x + y
}
// C側
void fill2(int x, int y)
{
    EM_ASM((mod.callAdd($0, $1)), x, y);
}

もう一つはJSで書いたコードを--pre-jsオプションでemccの生成コードの中に埋め込み, それをCの中でextern関数として呼ぶ方法.

// pre.js
var _call2JS = function(x, y) { /* _が必要 */
    return x + y
}
// C側
extern int call2JS(int x, int y);
int call2(int x, int y)
{
    return call2JS(x, y);
}
// emccでbuildするときに--pre-js pre.jsオプションを追加.

warning: unresolved symbolが出るけど動いてるようだ.

pre.jsの中ではES6のコードは書けないようでたとえば変数はletでなくvarを使う(正確にはasm.jsでサポートしている範囲? よくわからない). そうでないと意味不明なエラーに悩む(かなり時間を食ってしまった).

subprocess.CalledProcessError: Command
  '['emsdk/node/4.1.1_64bit/bin/node',
    'emsdk/emscripten/1.37.22/tools/js-optimizer.js',
    '/tmp/xxx/fill.bc.o.js.pp.js.mem.js',
    'noPrintMetadata',
    'JSDCE',
    'last',
    'minifyWhitespace']' returned non-zero exit status 1

最適化オプション-O1ではこのパスは通らないのでエラーにならない(-O2, -O3でエラー).

足し算する関数をいくつかの方法でざっくりとベンチマークを取ってみた(run.js). ベンチマークは本当にざっくりとであり, テストするたびに数割～2倍程度のぶれは発生するのであくまでそんなこともあったという程度の数値.

• testJS : WASMを使わずJSでx + y
• test0 : WASMのCでx + y
• test1 : WASMからEM_ASM_INTでJSのx + yを実行
• test2 : WASMからJSの加算関数を呼び出す

ChromeのWASMの呼び出しコストはかなり低いのに驚いた. 毎回evalしてそうなtest1よりtest2の方が速いのだろうと予想したが一応そんな傾向はある.

ただ1msec程度かかる処理を呼ぶならどちらでもよい. JSの制約に悩む可能性を考えるとEM_ASMの方が安全かもしれない.

EM_ASMはCの中での途中経過の出力をconsole.logに出す方法としては気軽にできてよさそうだ.

emscriptenにおける/dev/urandomの扱い

疑似乱数生成にLinuxでは/dev/urandomを使っているのだけどemccでどう変換されているのか不安だったので追いかけてみた. 結論から言うと大丈夫そう.

emccはファイルシステムをエミュレーションしていて

FS.createDevice ("/dev", "urandom", random_device);

していた. このデバイスを開くとrandom_deviceにいくのだろうと, そちらを見ると

var random_device;
if (typeof crypto !== "undefined") {
    var randomBuffer = new Uint8Array(1);
    random_device = (function() {
        crypto.getRandomValues(randomBuffer);
        return randomBuffer[0]
    })
} else if (ENVIRONMENT_IS_NODE) {
    random_device = (function() {
        return require("crypto").randomBytes(1)[0]
    })
} else {
    random_device = (function() {
        return Math.random() * 256 | 0
    })
}

window.cryptoはWASMが動く環境ならあるので. crypto.getRandomValuesを使うから暗号用途に使って大丈夫.

she.js

大分慣れてきれいに書けるようになってきたかな. emccはちょっと変わったことをしようとするとすぐツールが例外を出すの辛い. 次はNode.jsから呼ぶ方法を調べる.

『日本会議の正体』(青木理)

最近名前をよく見るなと思って読んでみた. 「にっぽんかいぎ」というそうな. 20年ほど前に複数の団体が合流してできた宗教団体のようなもので, 全国各地に支部があり神社なども多数関わっているとのこと.

「美しい日本の再建と誇りある国づくり」のために着実に邁進している. おそろしい.

『「海の宝石」とよばれる生き物ウミウシの大研究』(濱谷巌)

↓で紹介されていたのとは別のウミウシの本だけど, 色鮮やかで不思議な生態のものがたくさん紹介されていた. 写真もきれい.

ウミウシしか食べないウミウシとか, 海藻を食べてその葉緑体を体に取り込み光合成したエネルギーを使うウミウシとか凄まじい.

なんでこんなにさまざまな形に分化したのだろう.

『翼を持つ少女 BISビブリオバトル部』(山本弘)

ちょっと前にビブリオバトルを初めて見て, そこで紹介されていたので読んでみた. 多すぎて困るぐらいおもしろそうな本が紹介されている.

H2O

ポインタのNULL判定を間違えていたところがあったのでpull reqした.

鼻水

急に寒くてくしゃみばかり. 寝不足や疲れもたたってしんどい. 早く寝よう.

emscripten & WebAssembly night !! #5で発表

久しぶりに外部でしゃべるのでめちゃくちゃ緊張した. しかも六本木と六本木一丁目間違えて入館ぎりぎりになってしまったしエレベータわからんし.

発表自体はまあまあおもしろがってもらえたようだ. よかった.

ブラウザで動く準同型暗号と実際のデモ

Homomorphic Encryption demo

ブラウザで完結するとデモがやりやすくてよいな.

JavaScript

明日の準備のためにいろいろ作ってるけどしょうもないところでミスって動かなくて原因追求に悩むのが多発. 早く新しい技術を勉強しないとして効率化しないといかんな.

ROCA:Vlunerable RSA generation

CVE-2017-15361

Infineon Technologies社のチップなどで作られたRSA鍵に脆弱性. OpenSSLで作ったものは大丈夫らしい.

公開鍵nを小さい素数(3～167)で割った余りが特定の値になったときに危ないもよう. rocaで確認できる.

該当する公開鍵か否かをチェックしているコードはhas_fingerprint_realあたり.

primes # 3から167までの素数のテーブル
prints # 対応するなんらかの数字

n # 公開鍵
for i in range(len(primes)):
     if (1 << (n % primes[i])) & prints[i] == 0:
         return False # 安全
return True # 安全じゃない

とりあえず自分に関係してるものは大丈夫そうだった.

wrapper class

BLS demoのAPIがWASMの_malloc, _freeを使ってるのでとても使いにくかったのでC++ライクなクラスを被せた.

classがmallocのポインタを保持してるとdestructorでfreeしないといけないのでUint32Array a_で持つことにした.

freeは気にしなくてもよいがメソッド呼び出しの度にmallocしてそのポインタにa_にコピーしないといけない. でも使い勝手はずっとよくなるのでその方がよいだろう.

うまく行きそうなのでSHEでもその方針で進める.

strnlen

strnlen(const char *s, size_t n)はsが区間[0, n)に'\0'を含んでいないときはnを返すのだけど, PVS-Studioは常にn未満を返すという前提の警告を出していた. そのせいで正しいコードがエラーになっていたので指摘して次のバーションで修正してもらうことになった.

128bit整数に対するbsr

元ネタはナンプレの正規化　ステップ・バイ・ステップ その５.

__builtin_clzlはbsrのintrinsicなのだけど0かどうかを事前にチェックしないといけない. bsr自体はその機能を持っているので冗長. 更に結果を反転させてるのでそれも無駄だから嫌いなintrinsicの一つ(cf. bsfとbsr). 実際, (値の受け渡しは呼び出し規約が分かりにくくなるのでポインタに変更した上で),

// typedef unsigned __int128 mbit;
void left_most_bit(mbit* v) {
  uint64_t *a = reinterpret_cast<uint64_t*>(v);
  if (a[1]) {
    a[0] = 0;
    a[1] = 1ull << (63 - __builtin_clzl(a[1]));
  } else if (a[0]) {
    a[0] = 1ull << (63 - __builtin_clzl(a[0]));
    a[1] = 0;
  }
}

はclangだと

left_most_bit:
    mov    rax,[rdi+0x8]
    test   rax,rax
    je     .low
    mov    QWORD [rdi],0x0
    lzcnt  rax,rax
    xor    eax,0x3f
    mov    ecx,0x1
    shlx   rax,rcx,rax
    mov    [rdi+0x8],rax
    ret
.low:
    mov    rax,[rdi]
    test   rax,rax
    je     .zero
    lzcnt  rax,rax
    xor    eax,0x3f
    mov    ecx,0x1
    shlx   rax,rcx,rax
    mov    QWORD PTR [rdi],rax
    mov    QWORD PTR [rdi+0x8],0x0
.zero:
    ret

となった. 今回の場合はVCの_BitScanReverse64がスマートだと思う.

void left_most_bit2(mbit* v) {
    uint64_t *a = reinterpret_cast<uint64_t*>(v);
    unsigned long idx;
    if (_BitScanReverse64(&idx, a[1])) {
        a[0] = 0;
        a[1] = uint64_t(1) << idx;
    } else if (_BitScanReverse64(&idx, a[0])) {
        a[0] = uint64_t(1) << idx;
        a[1] = 0;
    }
}

これならxorも条件分岐も減ったコードが生成される. x64 Linux用のNASMで書くとこう.

global left_most_bit

segment .text
left_most_bit:
    bsr rcx, [rdi + 8]
    mov edx, 1
    je .low
    mov qword [rdi], 0
    shl rdx, cl
    mov [rdi + 8], rdx
    ret
.low:
    bsr rcx, [rdi]
    je .zero
    mov qword [rdi + 8], 0
    shl rdx, cl
    mov [rdi], rdx
.zero:
    ret

PVS-Studio

去年Microsoft MVPを受賞したときに1年間使わせてもらっていた. いろいろバグが見つかってよかったのだがライセンスが切れてしまった.

それでLinux版が欲しいので値段を聞いたら何故かもう1年分ライセンスをくれた.

とてもありがたいので早速WalBで試したらいくつかポカミスが見つかったので修正. 多分そのうちマージされる.

こないだのblueborneのAndroidのRCEのバグもこれを試してたら見つけられていたかもしれない.

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

typedef struct {
    char a;
    int b;
    long long int c;
} X;

X *func() {
    X *p = (X*)malloc(sizeof(X));
    if (p == NULL) return 0;
    memset(((unsigned char*) p + 1), 0, sizeof(X));
    return p;
}

A call of the 'memset' function will lead to overflow of the buffer '(unsigned char*)p + 1'.

最適化

ate-pairingとmclは殆ど同じロジック・コードなのになんで約1.5倍も速度差があるのかずっと気になってた.

それぞれの関数自体はそんなに差がない. いろいろ細かく調べてみたところ, どうやらate-pairingでやってる低レイヤーの関数の呼び出し規約を独自にしてレジスタの退避復元を省略している部分が結構効いているようだ.

うーん, それをLLVMでやるのは辛そう.

ブラウザ上でSHE

ペアリングベースの一度だけ乗算可能なSHEが動いた(she.html). テーブルサイズの設定を工夫しないと初期化に時間がかかったりエラーになるけどまずはめでたい.

WASM

int64_tを受け渡しするAPIだと途中でint32_tに切られたりしていろいろ不整合がでるようだ. 32ビット整数しかやりとりしないのが無難.

JavaScriptには64ビット整数が無いのにWASMにはあるのがまたややこしい.