P2P探訪 Raider その1 Bittorrent File Format

[Raider Purpose]
 P2Pについて学習するために、Raiderというメタファーのgithubリポジトリを作成しました。
 まずは、もっとも有名な Torrentプロトコルを実装してみようと思います。 
 
 私にとっては、BitTorrentの仕様書だけを頼りに実装するのは難しいことです。
 そこで、Raiderでは、以下のアプローチとっています。
  1. bittorrentについて、実現できそうなシナリオを作る。
  2. 調査しながら、コードを書く
  3. 評価して、次のシナリオを決める。

　今は最初に実現しようとしているのは、以下のようなものです。
　 # torrentファイルの読み込みと作成をする。
 　これなら、簡単に実現できそうですね!!
 

[Torrent file format]
# bencoding
Torrent file は bencoding によって構成されています。 まずは、bencoingを扱えるようにする必要があります。
bencodingは integer, string(byte array), list, diction で構成されています。
bencoding は以下のような簡単なルールでencodeされます。

  beninteger   : "i" [0-9]* "e"
  benstring    : [0-9]* ":"  # 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)*

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

# torrent file format
bencodingが扱えるようになれば、torrent fileから必要な情報を取得することができるようになります。
torret file から取得できる情報はどんなものかは、別の機会に解説します。ここでは、torrent fileには 2つのフォーマットがあることとデータ構造を説明します。

torrent fileでは、ダウンロード/アップロードの対象としているファイルが、ひとつの場合と複数の場合で、構造がすこしだけことなります。参考までにデータ構造を紹介します。

- single file pattern
bendiction 
  benstring "announce"
  beninteger "creation date"
  bendiction "info"
    beninteger "length"
    benstring "name"
    beninteger "piece length"
    bebstring "pieces"

- multi file pattern
bendiction 
  benstring "announce"
  beninteger "creation date"
  bendiction "info"
    benlist "files"
      bendiction
        beninteger "length"
        benlist "path"
           benstring
      bendiction
      ..
      ..          
    beninteger "length"
    benstring "name"
    beninteger "piece length"
    bebstring "pieces"

[Raider's parse system]
Bittorrent のbencodingのencode/decode方法はとてもシンプルです。Bittorrentのパースをチックすると良いでしょう。ですが、Radierではね LLライクな方法を採用しました。特に理由はありません。仕様から空で考えたら、別の実装になってしまいました。


- comment about LL parse 
LL については、 [*3] を参照してください。
簡単にコメントします。 LLは文法とJava Method が一対一で対応付けられます。
※ 機械的な作業で実現できます。

例えば、以下のような文法の場合
   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;}
 }

bencoding
https://github.com/kyorohiro/Raider/tree/master/Raider/src/info/kyorohiro/raider/util/bencode

torrent file
https://github.com/kyorohiro/Raider/tree/master/Raider/src/info/kyorohiro/raider/util/torrent

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