週刊nmosh - Cygwin64対応 / mini-gmpバックエンド / 多倍長ビット演算の難しさ

諸般の事情で環境を移行しているので細かい修正が続く。。冷静に考えると、pffiへの移行によりnmosh pluginは一度もリリースされないまま消えるのか。。まぁ開発期間が長いとそういう事も有るよね。(ちなみにGStreamer SDK対応もリリースされずに消える見込)

Cygwin64 対応

先週追加した --with-system-bdwgc を使用することで、Cygwin64でも普通に動くように。Cygwin64はまだまだ発展途中感が有るが、手元ではCygwin32よりも安定して動作している。あとはgitさえ安定して動けば移行できそう。
ハマったというか単純に頭が悪かったのはCygwin64には__CYGWIN64__は無いこと。Cygwin64を判別したければ、__CYGWIN__した上で__x86_64__を使う。これはCygwin FAQにも載っている( http://cygwin.com/faq.html#faq.programming.64bitporting-cygwin64 )。_WIN32と_WIN64は有り、昔は__CYGWIN32__だったのでついついやってしまう。

mini-gmp バックエンド

多倍長演算バックエンドをビルド時に選択可能にしようとしている。要するにLGPLなコードが使用できないシチュエーション用。
GMPにはmini-gmpと呼ばれる1ソース完結のサブセットが有り、速度はともかくGMP互換のインターフェースを実装している。これもLGPLなので単純にリンクするのはあまり意味が無いが、ビルドが非常に簡単になるというメリットは有る。かも。

今のところバックエンドの選択はCMakeビルドでのみ可能。MOSH_MP_MINI_GMP_DIRで、GMPのソースコードの位置を指定する。mini-gmpはインストールできないので、常にソースコードからビルドされる。
mini-gmpはRatnumが存在しないので、mpz(整数インターフェース)で実装するwrapperを用意している。今後、Crypto++の多倍長ルーチンもバックエンドとしてサポートする予定で、このwrapperはそちらでも使用される。

static inline void mpq_set_d(mpq_t res, double x){
    double m;
    int e;
    m = frexp(x, &e);
    /* Bias with DBL_MANT_DIG to extract integer portions of frac part */
    m = ldexp(m, DBL_MANT_DIG);
    e -= DBL_MANT_DIG;
 :

意外と覚えていなかったのが、float.hにあるDBL_MANT_DIG。double型からRatnumに変換するためには、double型の仮数部を整数で取り出す必要があるが、そのために、DBL_MANT_DIG分だけバイアスしてやる必要がある。仮数部と指数部に分けるにはfrexpが使えるが、そのままでは整数に落とせないので。

多倍長ビット演算

というわけで、本命のCrypto++バックエンドも作成しているが、地味に躓いているのは多倍長のビット演算。
SchemeというかR6RSの整数ビット演算は、整数を2の補数表現した場合のビット列に対して動作することを求めている。つまり、 -1 は、1が無限に続くビット列としてとりあつかう必要がある。
しかし、GMPやCrypto++の内部表現はSign-Magnitude、つまり、符号と絶対値を分けて持つスタイルになっている。このため、対象の数値の正負によって処理を分ける必要がある。
例えば、普通の整数に対する not 演算は、各々のビットを反転してやれば良いが、Sign-Magnitudeな多倍長整数では符号を反転して1を引く(1を引くは、実際には符号の正負で絶対値から1を引くか1を足すかが分岐する)操作となる。学校では2の補数表現を作るためにビットを反転して1を足すと習うが、ちょうどこの操作のビット反転の部分を移項した状況になる。

 多倍長整数を(符号/絶対値)のように表わす
 (not (+/1)) = (-/2)  ;; 1 をビット反転すると-2になる。(bitwise-not 1)  => -2
    ;; (+/1) =符号反転=> (-/1) =1を引く=> (-/2)
 (not (-/1)) = (+/0)  ;; -1をビット反転すると 0になる。(bitwise-not -1) => 0

... and/or/xorも作らないといけない。(正,正)は自明で、単純に絶対値部分に対して該当する論理演算を適用すれば良い。(負,負)はいわゆるドモルガン則(andやor)や普通の式変形(xor)で対応できる。式変形をワザワザ行うのは、負数に2引数の論理演算を行わないため。
例えば、andの場合は、両者にnotを適用してからorし、更にnotする。

(and (-/2) (-/3)) = (not (or (not (-/2)) (not (-/3)))) ;; ドモルガン則
                  = (not (or (+/1)       (+/2))
                  = (not (+/3))                        ;; (or 1 2) => 3
                  = (-/4) ;; (bitwise-and -2 -3) => -4

orも同様に、

(or (-/2) (-/3)) = (not (and (not (-/2)) (not (-/3)))) ;; ドモルガン則
                 = (not (and (+/1)       (+/2))
                 = (not (+/0))                         ;; (and 1 2) => 0
                 = (-/1) ;; (bitwise-ior -2 -3) => -1

xorはわざわざ書く必要もなく、(xor a b) == (xor (not a) (not b))。ちなみに、xorは(正,負)のパタンも簡単で、(xor a b) = (not (xor a (not b)))。
and/orの(正,負)が地味に難しい。。負の数には必ずnotを作用させる必要が有るので、引数の片方にだけnotが適用される事になる。このような式変形では、xorを含んだ2ゲート以上が必ず必要になってしまう。
後でBoostのmultiprecitionあたりで答え合わせをする。。