2011-07-31

Cryptographic

暗号技術のこと。
仕事柄よく使うのでSagittariusにもほしいなぁと思い実装中。わざわざJCE使って鍵生成とか、暗号、複合をするのは結構面倒なのでというのが主な動機。
とは言っても中身自体を実装するのは骨が折れるのでlibtomcryptをバンドルしてそのラッパーみたいな感じにしている。
ちなみにこのlibtomcryptがすごくよくできていて、どうしたらこんなきれいな設計できるのかちょっと嫉妬。ドキュメントもすごくしっかりしているという。う~ん、見習わないと。

そんな素敵ライブラリなのだがECBとCBCモードで必要になってくるパディングは自前でやらないといけないということなのでとりあえずPKCS5のパディングを実装することに。理由はJCEのデフォルトだからというだけ。
っでググって見るとあんまり日本語の資料に引っかからない。しょうがないので仕様書の方を確認してみた。
仕様書はここ→RSA Laboratories - PKCS #5: Password-Based Cryptography Standard
おもむろにバージョン2.1のPDFを開いて「Padding」で検索。
3頁の項目4に記述を発見。
4. Concatenate M and a padding string PS to form an encoded message EM:
EM = M || PS ,
where the padding string PS consists of 8-(||M|| mod 8) octets each with value 8-
(||M|| mod 8). The padding string PS will satisfy one of the following statements:
PS = 01 — if ||M|| mod 8 = 7 ;
PS = 02 02 — if ||M|| mod 8 = 6 ;
...
PS = 08 08 08 08 08 08 08 08 — if ||M|| mod 8 = 0.
The length in octets of the encoded message will be a multiple of eight and it will
be possible to recover the message M unambiguously from the encoded message.
(This padding rule is taken from RFC 1423 [3].)
要するに8からデータの長さを8で割った余りを引いてその値を新しいデータに値の数だけ足すということ。
余りが0だった場合は8を8個末尾に追加。

なるほどね。

ちなみに、こんな感じになる予定。
(define key (string->utf8 "8bytekey")) ;; DES requires 8 byte key
(define des-cipher (cipher DES key :mode CBC_MODE :iv (make-bytevector 8) :padder pkcs5-padding)
(encrypt des-cipher (string->utf8 "data to encrypt"))
「:padder」キーワードは手続きを受け取り、パディングとアンパディングを行う。
キーワードを「padder」にしようか「padding」に使用かは悩み中だが、多分「padder」でいいだろう。

2011-07-27

Syntax-caseめぇ・・・

本当に実装者泣かせだ(僕だけ?)
これが動かない
スコープを曲げる
以下引用
(define-syntax let/scope
  (lambda(x)
    (syntax-case x ()
      ((k scope-name body ...)
       #'(let-syntax
             ((scope-name
               (lambda(x)
                 (syntax-case x ()
                   ((_ b (... ...))
                    #`(begin
                        #,@(datum->syntax #'k
                             (syntax->datum #'(b (... ...))))))))))
           body ...)))))

(let ((x 1))
  (let/scope d1
    (let ((x 2))
      (let/scope d2
        (let ((x 3))
          (list (d1 x) (d2 x) x))))))  ;; ⇒ (1 2 3)
これがunbound variable xで&assertionを投げる。
(キャッシュを使ってるともっとひどくて、マクロ展開時に死ぬ。何故だ?)

なぜ動かないか、「足りないからだ、憎しみ(識別子の中の環境のこと)が・・・」(by うちはいたち)

問題になるのはdatum->syntaxに渡されるテンプレート用の構文オブジェクト = 識別子。
Sagittariusでは他のR6RS処理系と違って、「k」は使い回しされる。かつ、「k」はここでは「let/scope」そのものになり、大域に出現した識別子となる。(多分これがもとでbound-identifier=?が上手く動かない)
問題はここからで、グローバルな識別子はそれ自身に環境を持っていない。持つ必要がないから。
そうすると、datum->syntaxが渡されたテンプレートに梱包されている環境(グローバルなので空)を元に新たな識別子を作り、結果、上記の(d1 x) (d2 x)はグローバルな呼び出しとなる。
突き止めるまでに1時間くらいかかったが、原理は分かった。問題は、ない情報をどこから引っ張り出してくるかということになる。
無知な頃に(今でもだが)作った(パクった?)部分が多々あるので、コードの読みにくさもあいまってマクロ周りは出来がひどい。リファクタリングも兼ねて一度見直すべきだろうか?

LGPL vs MITライセンス

SagittariusはMIT(修正BSD?)ライセンスで配布しているのだが、そのなかにLGPLで書かれたスクリプトを入れることは可能なのだろうか?という疑問。
MITライセンスはほぼ何でもありというライセンスなのだが、LGPLはライブラリが静的にリンクされる場合に限りGPLと同様のコピーレフトを持つと解釈できる。
でも、スクリプトファイルをそのまま(若干の改変あり)で配布する際、こいつは動的にリンクされるので、このファイルだけを公開すればMITライセンスと共存できる、はず。
そもそも、スクリプトファイルの実行って動的リンクなのか?

バグつぶし

ドキュメントを書いていると、R6RSから少し拡張した機能がきちんと働いているかテストしていないことに気づいたり、一貫性の問題で新たに機能を足したりすることがある。
例えば、vector-refはR6RSでは2つの引数を取るが、Sagittariusではオプション引数を取ることができる。第2引数がベクターの範囲外だった際にその引数の値が返されるというものである。アイデアはGaucheからもらってます。
っで、その機能を使ったことないなぁと思ったので試してみたらまったく上手く動いていない。その上、範囲外の値を渡したらセグったという落ちも。(RacketのR6RSテストスイートはよくできてるし、割とそれに頼りまくっているが、エラーケースはあんまりテストされてないっぽい)
こういうことが実は結構あって、ドキュメント書きながらコンソールまたはEmacsで動作を確認→不具合を見つける→修正という作業が頻繁に起こる。以下に適当に作ってるかわかるなぁ・・・リリースしたくせにWindows版では動いてない機能とか・・・(socketのことだよ!)
不具合が見つかって修正されるのはいいことなのだが、これくらいのものはもっと以前に見つけてないといけない気がする。テストケースを足していく必要があるということか。

2011-07-21

FFIが動いた!!!

libffiを使っているので、ある意味当たり前なのだが、こんなコードが動いた。
(define kernel32 (open-shared-library "kernel32.dll"))
;; 構造体もサポートしてるぜ!!
(define-c-struct systemtime
  (unsigned-short year)
  (unsigned-short month)
  (unsigned-short day-of-week)
  (unsigned-short day)
  (unsigned-short hour)
  (unsigned-short minute)
  (unsigned-short second)
  (unsigned-short milliseconds))

(let ((proc (c-function kernel32 void GetLocalTime (void*)))
      ;; ughh
      (sys (c-malloc (size-of-c-struct systemtime))))
  (proc sys)
  ;; アクセスの仕方は考えた方がいいかもしれない。ちょっとダサい。
  (print (c-struct-ref sys systemtime 'year)) ;; 2011
  (c-free sys))
ちなみにコールバックも兼ね備えていて(まぁlibffiのおかげだが)、こんなこともできる。
(define lib (open-shared-library "add.so"))
(define array (u8-list->bytevector '(6 5 3 4 1 7 2)))
(let* ([qsort (c-function lib void quicksort (void* size_t size_t callback))]
       [compare (c-callback int (void* void*) 
       (lambda (x y)
         (- (pointer-ref-c-uint8 x 0)
     (pointer-ref-c-uint8 y 0))))])
  (qsort array (bytevector-length array) 1 compare)
  (display array)
  (free-c-callback compare))
add.soなんてのを使ってるのは、cygwin上でのlibcがどれだか分からなかったため。。。
単にqsortの自力実装なんだけど、まぁ動く。
実行結果が、ソートされてないのはmoshもだったので気にしない(でいいのか?)

できればlibffiをバインドしたいんだけど、あんなに複雑なconfigure.acをCMakeLists.txtにできる気がしないので、後回しということにしてしまう。。。

2011-07-17

キャッシュが遅い

キャッシュを作って早くなったと思っていたのだが、実は遅かった。
コマンドラインオプションに--disable-cacheがあるのだが、それを使ったのと、普通にキャッシュを呼んだのとで0.3秒ほど違いがでる。単に(import (rnrs))と書いたファイルを実行するのにだ。
プロファイルを取ろうとしたらgprofがOut of Memory errorとか言いやがるので、timeコマンドの意味を調べてみた。
userが計算時間、systemがI/O、realがトータル。
これを頭に入れて再度時間を計測。

$ time ./build/sash test3.scm
./build/sash test3.scm 1.37s user 1.06s system 93% cpu 2.603 total

$ time ./build/sash --disable-cache test3.scm
./build/sash --disable-cache test3.scm 1.92s user 0.20s system 89% cpu 2.368 total

I/Oか。計算時間もそこまで差が無いように見えるなぁ。
3倍早くなった気がしたのは、作成時間がかかってただけだな。
見直すか。

追記:
見直した。ファイルの内容を一発で取ってきてI/Oの回数 = ファイルの数にしてみた。結果

$ time ./build/sash test3.scm
./build/sash test3.scm 0.87s user 0.19s system 89% cpu 1.184 total

倍早くなった。計算部分はキャッシュ自体を小さくするか、より効率的にするしかないな。
ただ、この方法はかなりメモリ効率が悪い。何とかしたいところではある。
(そうは言っても、コンパイルにものすごくメモリを食うので、結果的にキャッシュを使った方がメモリ使用量は少ないが)

2011-07-15

Lady Gaga

ちょうど今TVに出てて、生(かどうかは知らんけど)で歌っていた。
正直今まで、色物な歌を歌ってる奇抜な衣装のねーちゃんくらいのイメージしかなかったんだけど、歌唱力が半端なかった。
PVとかCDの音だとそこまで分からないんだけど、マジでうまい。同じレベルの歌手があまり浮かばないくらい。
結構踊りも激しかったんだけど、全部歌ってたし、すげ~なぁ。トップアーティストってのはこういうのなんだなぁとちょっと感動した瞬間だった。
曲自体はキャッチーだけど、あんまり好きではなかったりするが・・・(^^;

2011-07-12

R6RSのレコードにあるprotocolが地味に便利だった件

あまりに複雑すぎる(とどっかで見た)と不評なR6RSのレコードだが、単に使うだけなら結構便利な件。
特に今までつかってなかったけど、protocolが結構便利。
例えばこんな例:
(define-record-type something
  (fields (mutable f1)
          (mutable f2)
          (mutable f3)))
上記のレコードsomethingはfieldsとしてf1~f3まで持つけど、初期化時にコンストラクタに値を渡さないかもしれない。上記の例では必ず
(make-something #f #f #f)
なんて書かないといけないが、protocolを定義すると事情が変わってくる。
(define-record-type something
  (fields (mutable f1)
          (mutable f2)
          (mutable f3))
  (protocol (lambda (p)
              (lambda args
                (let-optionals* args ((f1 #f)
                                      (f2 #f)
                                      (f3 #f))
                  (p f1 f2 f3))))))
let-optionals*は探せばいろいろあると思うけど、Sagittariusでは(sagittarius control)ライブラリで提供。こうすると上記のmake-somethingがこんな風に書ける
(make-something 'value)
ここまでは、まぁ割と当たり前なんだけど、Sagittariusの一つの特徴としてキーワードを認識する。っで、キーワードを使ってこんな風に書ける。
#!compatible ;; キーワードはr6rsモードでは動かない
(import (rnrs)
        (sagittarius control)) ;; let-keywords let-keywords*もこの中
(define-record-type something
  (fields (mutable f1)
          (mutable f2)
          (mutable f3))
  (protocol (lambda (p)
              (lambda args
                (let-keywords args ((f1 #f)
                                    (f2 #f)
                                    (f3 #f))
                  (p f1 f2 f3))))))

(make-something :f3 'value)
let-keywordsはGaucheからもらってます。これが地味に便利。フィールドが少ないうちはそんなに感じないけど、10個くらいあって、7番目だけ値を入れたいなんて場合にこれが活躍してくる。難点は、全部に値を設定したい場合に一々キーワードを書かないといけないところか。ま、トレードオフだろう。

2011-07-11

Harry Potter

最初の映画を見てたりするのだが、今更ながらに気づいたこと。
ずっとハーマイオニーだと思ってたのだが、彼女の名前はHermioneでよく聞くと、ハーミオニに近いこと。
っで、オランダ語の字幕にはHermiolineと何故かLがくっついてること。

どうでもいい話。

ところで、ハリーポッターって何がハリーを特別にしてるの?家系?映画見ててもその辺全然説明無くて、いきなりセレブだって言われるからさっぱり分からん、

2011-07-10

ドキュメントを書き始めた

いろいろ何を使おうか悩んでいたが、別にtexinfoとか自前で何か作るとかは馬鹿らしいなぁと思ったので、結局OpenOffice.orgのWriterにした。
それでいいのか?という疑問は未だに付きまとうけど、単なるAPIドキュメントという側面だけではないようにしたいと思うと割としっかりしたドキュメント作成用のソフトが要るようになる。わざわざテキストファイルで書いてくTexとかはあまりに面倒だし、今から覚えるのも億劫だったという理由から。
最終的にはOOoフォーマットからLaTexか何かに変換してHTMLを出力という形に持っていこうとは思っている。OOoフォーマットだとソフト持ってないと読めないし。

ドキュメントと書いてて思ったのが、かなりの分量が必要になるということ。R6RSで規定されている関数とかも全部書いているからなのだが、かなり凹みそうになる。なぜそんな部分まで必要になるかというと、R6RSで規定されている関数を拡張しているものがあって、単純に仕様書にポインタを指すということができないから。
割とコピペで済ませる部分が多いが、これをやってて仕様を満たしていない部分を発見したりするから割と有用かな(今まで必要な部分しか読んでなかったというのもあるが)。時間かかるけど。

2011-07-09

とりあえず一旦完了

Compiled Cacheの実装が一旦完了した。キャッシュから読み込むと3倍くらい早いのでまずまずだろう。
いくつか問題点があって、
・依存関係にあるキャッシュが変更された際に上手く動かない
・キャッシュ自体が壊れていた場合に上手いことエラーハンドリングしない
などというところがとりあえず分かっている。
が、問題だなぁと感じてから直すことにする。

ほしいと思って投稿してからほぼ1週間これの実装にかかったわけだ。結構かかったな。
まぁでも、それなりに待てる時間まで実行時間が短縮されたので無駄ではなかっただろう。

2011-07-07

はまってたこと

ずいぶん長い間気づかなかったが、Cygwinのマウント形式に長いことはまっていた。
Cygwinはバージョン1.7からfstabが使えるのだが、それを最初に記述した際に、NTFSをtextでマウントしていたみたい。
っで、賢いのかバカなのか分からないけど、Cygwin上でread(freadではない)を行った際に、\r\nが\nに自動的に変換されていた。
バイナリで扱ってほしいのに、そんなものまでテキストにされていたとは。

Twitterでつぶやいた1バイトスキップされる問題はこれだったということ。こんなの中々気づけないよ。