憂鬱な午後のひととき

『ニコリ』

8年振りぐらいに買った. 新しいパズルがいろいろ載ってる. ぼちぼちやっていこう.

conversion to unspecified boolとexplicit bool

@yuguiさんに『Modern C++ Design』にoperator boolの実装があるよ教えていただいたのでダンボールをひっくり返して探してみる.

class X {
    const char *p_;
    class BoolType {
        void operator delete(void*);
    };
public:
    X(const char *p) : p_(p) {}
    operator const BoolType *() const
    {
        static BoolType b;
        return p_ ? &b : 0;
    }
};

BoolTypeというdeleteできないクラスを作り, そのstatic変数のポインタを返す. static変数が絡んでるので単純なoperator boolよりはコストがかかるかも. 実際asmコードを見ると余計な値との比較が行われていた.

// gcc-4.9.1
    xor eax, eax
    test    rdi, rdi
    je  .L7
    mov eax, OFFSET FLAT:_ZZNK1XcvPKNS_8BoolTypeEEvE1b
    test    rax, rax
    setne   al

// VC2013
    xor     eax, eax
    test    rcx, rcx
    lea     rdx, OFFSET FLAT:BoolType
    cmovne  rax, rdx
    test    rax, rax
    setne   al

// clang 3.5
    testq   %rdi, %rdi
    setne   %al

clangは単純なoperator boolと同じコードになっていた.

Boostなどで使われているconversion to unspecified boolイデオムだとstatic変数は使わない.

class Y {
    const char *p_;
    typedef void (Y::*BoolType)() const;
    void dummy() const {}
public:
    Y(const char *p) : p_(p) {}
    operator BoolType() const
    {
        return p_ ? &Y::dummy : 0;
    }
};

こちらだともうちょっとよくなってるかも. ところが, gccでのasmでのコード生成は意外にも上記コードと同じだった. clangは逆にstatic版より複雑(=VCのstatic版とほぼ同じ)コードを生成した. VCはclangのstatic版と同じすっきりコードになった.

// clang 3.5
    testq   %rdi, %rdi
    movl    $_ZNK1Y5dummyEv, %eax
    cmoveq  %rdi, %rax
    testq   %rax, %rax
    setne   %al

// VC
    test     rcx, rcx
    setne    al

これはなかなか予想外. ところでせっかくC++11で入ったexplicit boolだが, レガシーなコードから if (x == 0)やif (x == NULL)などの使い方をされていると先日書いたようにnullptr_t以外との比較演算子を定義しないといけない. しかもgccではどうやってもNULLとの比較で警告が出る(いくつか試した限りでは). なかなか悩ましい.

NULLと0

nullptr_tでいいかと思ったけど使ってる側はそうじゃないから駄目だった. 今更だけど0とNULLとnullptr_tて全て違う型かもしれないんだな.

#include <stdio.h>
#include <cstdint>
#include <typeinfo>

int main()
{
    printf("type of 0 = %s\n", typeid(0).name());
    printf("type of NULL = %s\n", typeid(NULL).name());
    printf("type of std::nullptr_t = %s\n", typeid(std::nullptr_t).name());
}

type of 0 = i
type of NULL = l
type of std::nullptr_t = Dn

めんどくさい.

NULLとの比較

あるクラスにNULLと比較するメソッドを追加したい. C++11ならクラスXに

bool operator==(std::nullptr_t) const

を追加するとするとX x; x == NULL;が通る. ただ古いコンパイラにも対応したいなと思うとちょっと困る. 普通NULLは0で型はintだと思うのだけどgccではNULLの型はlong.

C++の規格でもNULLの型は処理系依存で0Lはありだったりする. だから

#ifdef __GNUC__
  typedef long NullType;
#else
  typedef in NullType;
#endif
bool operator==(NullType) const

とすればいいと思った. ただgccでx == NULL;をコンパイルすると警告が出てしまう.

warning: passing NULL to non-pointer argument 1 of
'bool X::operator==(long int) const' [-Wconversion-null]
x == NULL;

x == 0やx == 0Lだと文句は言われない. なんでだろうとstddef.hをちゃんと見るとNULLは__nullだった.

// stddef.h
#ifdef __GNUG__
#define NULL __null
#else   /* G++ */
#ifndef __cplusplus
#define NULL ((void *)0)
#else   /* C++ */
#define NULL 0
#endif  /* C++ */
#endif  /* G++ */

こいつが上の警告を出させてるようだ.

clangでもNULLは__nullだったけどその警告は出さない. とか試していたらVC2010でもstd::nullptr_tは対応していた. 使えないと思い込んでいたけど対応してるならそれでいいか.

Visual Studioのiterator

VCのiteratorはdebugモードではreleaseモードに比べてサイズが大きい. 64bitだとreleaseモードでは8byteなのに対してdebugモードでは24byte. これはたとえばvectorでうっかりpush_backして無効化されてしまったiteratorを参照したときに気がつくような情報が入っている [Debug Iterator Support].

これは_ITERATOR_DEBUG_LEVELマクロの値を変更することでreleaseモードと同じ挙動にしたりできる[_ITERATOR_DEBUG_LEVEL].

何が入ってるのかの情報をもう少し正確に知る必要が出たので調べてみた. ヘッダを見ると_Ptrをprivateに持ってるのは分かるがそれ以外がすぐに見当たらない. 丹念に読めば分かるはずなのだけど, templateが複雑に絡んでるのでよくわからない. こういうのはIDEに任せるといいだろうということで#define private publicにして実行してみる.

#define _ALLOW_KEYWORD_MACROS
#define private public
#include <stdio.h>
#include <vector>
typedef std::vector<int> IntVec;

int main()
{
    IntVec iv;
    iv.push_back(123);
    IntVec::iterator i = iv.begin();
}

単に#define private publicとするとキーワードをマクロに使うなとVCがエラーにしてしまう. それを防ぐために先に_ALLOW_KEYWORD_MACROSを定義する.

IDEで上記コードを書いてi.のところで補完させるとメンバーや型が表示されるのでそれをみながらあたりをつける(便利だなあ). releaseに比べて16byte大きいのは二つのメンバー_Myproxyと_Mynextiter用だと分かる. _Myproxyはこの場合自分自身を指していた. こいつは_Mycontというメンバを持ち, これはコンテナ本体(iv)のポインタを持っていた. だからiv.empyt()のときでもこれは0ではない. この瞬間は_Mynextiterは次はないので0.

メンバ変数の名前が分かったのでそれらの位置情報をとるために次のコードを書く.

#define _ALLOW_KEYWORD_MACROS
#define private public
#include <stdio.h>
#include <vector>

typedef std::vector<int> IntVec;

int main()
{
    IntVec iv;
    iv.push_back(123);
    IntVec::iterator i = iv.begin();

    printf("sizeof(i)=%d\n", (int)sizeof(i));
    printf("sizeof(_Ptr)=%d\n", (int)sizeof(i._Ptr));
    printf("*_Ptr=%d\n", *i._Ptr);

    printf("ptr &*i  =%p\n", &*i);
    printf("ptr i    =%p\n", &i);
    printf("ptr proxy=%p\n", &i._Myproxy);
    printf("ptr next =%p\n", &i._Mynextiter);
    printf("ptr _Ptr =%p\n", &i._Ptr);

    printf("offset proxy=%d\n", (int)offsetof(IntVec::iterator, _Myproxy));
    printf("offset next =%d\n", (int)offsetof(IntVec::iterator, _Mynextiter));
    printf("offset _Ptr =%d\n", (int)offsetof(IntVec::iterator, _Ptr));

    printf("val proxy=%x\n", i._Myproxy);
    printf("val next =%x\n", i._Mynextiter);
    printf("val _Ptr =%x\n", i._Ptr);
}
>cl t.cpp /EHsc /MDd
sizeof(i)=24
sizeof(_Ptr)=8
*_Ptr=123
ptr &*i  =00000000004607C0
ptr i    =00000000002CFB00
ptr proxy=00000000002CFB00
ptr next =00000000002CFB08
ptr _Ptr =00000000002CFB10
offset proxy=0
offset next =8
offset _Ptr =16
val proxy=464330
val next =0
val _Ptr =4607c0

offsetを調べてみると_Ptrはiteratorの先頭にあるのではなく+16byte目にあるのだった.

i = iv.begin();

+0        +8            +16   +24
+---------+-------------+-----+
|_Myproxy | _Mynextiter | _Ptr|
+----|----+-------------+--|--+
     v                     v
    _Mycont               &iv[0]
     &iv

簡単だけどこの構造が分かれば当面は十分かな.

Office365の認証

会社で使うことになって金曜日の午後に認証しようとしたのだけどどうやってもうまくいかない. 他の人はできてるので自分のパソコンの何かが悪いのだろうけどわからない. ただ別のマシンでやっても同じ現象になったのでますますわからない.

とかで金曜の夜は無駄に疲れたのだが, 火曜日に試したら何事もなく通った. あとで情シスに聞くと金曜日の夜はトラブルが多いらしい. マイクロソフトのサービスってMSDNの作りにしろ, connectにしろへちょい気がする.

テスト

開発中のツールのテスト中にコマンドの操作ミスをしたらkernel driverがNULLアクセスで落ちた. あらまー, と思いながら原因を探る. 少々再現方法の確定に手間取ったが報告したら別のマシンでは発生しない.

kernelのバージョンを確認したらubuntuの3.13.0-32では発生するけど3.13.0-35では直ってた. 1カ月ほど前に直ったばかりだったらしい. 自分たちがやるはめにならずによかった.

Re:FpMgr

ぼけていた. これじゃあmpz_classと共存できない. デストラクタを正しく走らせるにはどこか妥協が必要だなあ. sizeof(Fp) = 64は死守したいのだが.

FpMgr

5日の件, 現在のFpクラスのstaticメンバ変数を取り替えられるようにしたらいいだろうか. それらをFpMgrクラスでもらせる. Fpの元自体にはどのmoduloで演算するかの情報はもたせない.

FpMgr fp;
fp.setModulo("13423423...");
Fp x(fp, 3);
Fp y(fp, 5);
fp.add(z, x, y);

みたいな. この問題点はFpクラスに対してoperator+()やoperator<<()などの演算子を定義できないこと. そのためいちいち, fp.addとかfp.toStr(x)みたいにどのFpMgrを使ってるかを指定しないといけない.

ただ楕円曲線や上位のクラスメソッドがFpMgrをメンバに持ち, そいつらがoperator+(Fp, Fp)を持るのはありかもしれない. それならEcのメンバ関数の中ではz = x + y;みたいに書けるかな.

固定有限体クラスライブラリmieメモ

最近, ペアリングライブラリate-pairingを 暗号アプリケーションのパーツとして使ってるという知らせや, 使い方の問い合わせがちらほら来るようになった. とてもありがたい.

けれどもこれは速度最優先で作ったので, 実際に他人に使ってもらえるようになると不満もいろいろでてくる. 問題点は大きく二つ.

• なりふりかまわない最適化をしていたのでコードの見通しがとても悪い.
• パラメータが固定で埋め込まれているので変更するのがとても難しい.

それで, GMPみたいに汎用ではないけど, そこそこ自由度のある有限体クラスライブラリ(160～256bitをターゲット)を作っていた. これを使ってate-pairingを再構成すれば多少速度は落ちるかもしれないけど柔軟性があがるんじゃないかという目論見. その本来の目的はまだやってないのだけど, これはこれでそれなりに使えるようになってきた. Lifted-ElGamalとか.

ただ, そうするとこれ自体がより柔軟に使いたいと思えるようになってきた. 今は有限体クラスFpは素数pの値は固定で使う. 複数のFpが欲しい場合は, Fpはstruct tagを持つtemplateクラスなので異なるtagに対してインスタンス化して使うことになっている. Montgomeryを使ったりGMPを内部で使うやつも全て異なる型になっている.

// GMPを使ったパラメータ可変の楕円曲線クラス
typedef mie:EcT<mie::FpT<mie::Gmp>> EcGmp;

// 256bit素数専用の高速なMontogomery乗算を使った有限体クラス
typedef mie::MontFpT<4> Fp256;

// Fp256を使ってsecp256k1の楕円曲線暗号クラスを生成
mie::EcT<Fp256>::setModulo(mie::ecparam::secp256k1.p);

それはFpの元a, bに対してa + bを計算するときにpの情報をaやbそれぞれが持ちたくないから. 1クロックでも削りたいので実行時にディスパッチもしたくない.

だがそうすると, アプリケーションでpの値をダイナミックに変更したいとき必要な数だけFpクラスを用意する必要がありとてもめんどい. Fpは単一のクラスにして最小限のコストで柔軟にするにはどうするのがよいだろう.

たとえば256bit整数のときはsizeof(Fp)は32(byte)であってほしい. mallocはしたくないしvtblも埋め込みたくない. うーん.

日本応用数理学会JANTセッション

プロジェクタのトラブルなどもなく無事終了. ほっとした.

「Diophantine method in determining problem of lattice points」が面白かった.

「複素平面上のある条件を満たす整関数fが自然数nに対していつでも整数値をとるなら, そのfは多項式.」 という定理があるらしい(Polya).

今回の発表はその条件を少し緩めて, 「十分大きいnに対してf(n)が殆ど整数値ならfはQ係数多項式になる」といもの.

その「殆ど整数値」という条件が f(n)の小数点部分がe^-663143nより小さいというもの.

n = 1でも4.5 x 10^-288000なのでその「殆どっぷり」がすごい.