P2P探訪 Raider その1-1 Bencoding

前回の記事を書き直しました。説明不足を補います。

 課題1 Torrent File に記載されている情報を読み込みたい。
BitTorrent のプロトコルを学習するに当たって、実際に、Torrentクライアントを実装することにしました。
まず最初に、TorrentFileに記載されている情報を読み取ることから始めたいと思います。

Torrentファイルは、bencode というルールで、記述されています。
そこで、
1. Bencodingを扱えるようにする。
2. Bittorrentファイルを読み込めるようにする。
の順に問題を解決していくことにしました。

というわけで、この記事ではBencodingについて説明します。

Bencoding
bencodingは integer, string(byte array), list, diction のデータ型を持ちます。
なので、この4つデータ型のデコードとエンコードができるようになれば、
bencodingを扱えるようになったことになります、

具体的に、以下のようなルールでエンコードされいます。
  beninteger   : "i" [0-9]* "e"
  benstring    : [0-9]* ":" <bytes array/string> 
　    # bytes array/string length is prev [0-9]*.
  bendiction   : "d" dictelements "e" 
  benlist      : "l" listelements "e"
  benobject    : beninteger | benstring | beniction | benlist
  listelements : benobject (benobject)*
  dictelements : benstring benobject (benstring benobject)*

といった感じです。
例えば、
  Integerで、1を表したい場合は、"i1e"
  Stringでabcを表したい場合は、"3:abc"
  上記を含むListを表したい場合は、"li1e3:abce"
  といった感じで表せます。


また、bencodingは簡単にパースできるように工夫されています。
簡単といえるのは、先頭1文字で、どのデータ構造でできているかが判断できるようになっているからです。

なので、bencodingのdecoderは、以下のようなシナリオで実現できます。
1. 一文字読み込む。
2. どのデータか判別する。
例えば、 'i' ならば、integer、's'ならば、stringといった感じです。
3. データ形式に応じて読み込む。
4. 1に戻る。


RaiderでのParse方法
Bittorrent のbencodingのencode/decode方法はとてもシンプルです。
Bittorrentのbencodingに関する部分のコードをチックすると良いでしょう。ですが、Radierでは LLライクな独自の方法を採用しました。
特に理由はありません。仕様から空で考えたら、別の実装になってしまいました。

パースの仕組みについて、簡単に解説します。 LLでは文法とJava Method が一対一で対応付けることができます。
なので、対応付け方法がわかれば、機械的な作業になります。
※ なので普通は、antlrだとか javaccとか、yaccとか　bisonとか　ツールを使って実現したりします。


例えば、以下のような文法の場合
   benstring    : "i" [0-9]* "e"
   beninteger   : "i" [0-9]* "e"
   benobject    : beninteger | benstring

以下のような感じで一対一の対応で書けます。
 static void benstring(reader) throws xxException {
    try {
       reader.mark(); 
       if(check(string grammer)) {
       } else {
          reader.backtoMark(); // パースに失敗した時に、ポインターの位置を元に戻す。
          throw xxException;
       }
    } finally {
      reader.releasemark();
    }
 }

 static void beninteger(reader) throws xxException  {
    try {
       reader.mark();
       if(check(integer grammer)) {
       } else {
          reader.backtoMark(); // パースに失敗した時に、ポインターの位置を元に戻す。
          throw xxException;
       }
    } finally {
      reader.releasemark();
    }
 }
 static void benobject(reader) throws xxException {
     try {benstring()}catch(xxException e){}
     try {beninteger()}catch(xxException e){throw e;}
 }



[reference]
- 成果物、bencoding
  https://github.com/kyorohiro/Raider/tree/master/Raider/src/info/kyorohiro/raider/util/bencode

- Torrent spec
  http://en.wikipedia.org/wiki/Torrent_file
  http://www.bittorrent.org/beps/bep_0003.html
  http://sourceforge.net/projects/bittorrent/
  
- LL Parser
  http://pragprog.com/book/tpdsl/language-implementation-patterns