Dart で Torrentクライアントを作ろう ( 4 ) Torrentファイルを読み込む

Torrentでのデータのダウンロード処理は、Torrentファイルを読み込む所からはじまります。
それにならい、実際に Torrent ファイルを読み込み、必要な必要な情報を取得するところからはじめて見ましょう。

Bencodingとは

• Torrentファイルはbencodingて書かれている。
• Bencodingは、Integer、String、List、Dictionaryを扱える。

Torrentファイルは Bencoding

Torrentファイルは、bencoding という形式で書かれています。Torrentファイルに記載されている事を読み解くためには、bencding/bencode を解釈できるようにならなくてはなりません。
まずは、Bencosingのパーサーを書いていきましょう。Bencodingは、文字列、整数、辞書、リストの4つのデータを扱うことができます。

Format

beninteger : “i” [0-9]* “e”
benstring : <string length> “:” <bytes array string> 
string length : [0-9]*
bendiction : “d” <dictelements> “e”
benlist : “l” <listelements> “e”
benobject : beninteger | benstring | bendiction | benlist
listelements : benobject ( benobject)* 
dictelements : benstring benobject (benstring benobject)*

そして、上記のようなフォーマットで書かれています。

文字列を扱える

Bencode で文字列は、「<文字の長さ> “:” <文字>」という形式で書かれています。例えば、「torrentという文字列は、bencodeでは、「7:torrent」と書く事ができます。
もうひとつ、bencode の文字列は、バイトデータとして扱われる事もあります。IPアドレスのバイト表示や、Hash値などの非アスキーな範囲のデータなども、本形式で扱います。
例えば、日本語で「アイ」はSJISで表現すると「0x83, 0x41, 0x83, 0x43」の4バイトで表現できます。この場合、Bencodeでは、「4:アイ」と表記できます。

例

oden
　　4:oden
オデン SJIS
　　6:オデン
SHA1Hashデータ
       20:<SHA1 Hashデータ>

整数を扱える

整数は0より大きな値を表現するデータです。「“i” *[0-9] “e”」という形式で表すことができます。例えば、1024は「i1024e」と書くことができます。
ファイルのサイズ、ポート番号、といった、数字で表現できるものに利用します。

例

2
  i2e
1024
  i1024e
 65526
  i65526e

リストを扱える

リストはデータ構造のひとつです。順序ありのデータを保持する事ができます。例えば、IPアドレスの一覧、ファイルの一覧、といったものを表現するのに使用します。

例

あいうえお、かきくけこ
    l12:あいうえお12かきくけこe
128、 100、500
   li128ei100ei500ee

辞書を扱える

辞書ばデータ構造のひとつです。キーワードとデータを関連づけて保持する事ができます。
例えば、RPGゲームの主人公のパラメータとして、名前、性別、レベル、得意な魔法、といったものが設定されているとしましょう。辞書はこの、バラメータ名とその値を関連づけます。「名前」というキーワードで、主人公の名前を記録したりできます。

例

例えばlevelが13で、nameが山田、を辞書で表現すると、di5:leveli13e4:name4山田e

今後の表記について

今後、データ構造を表す場合は、以下の表記を利用します。
リスト
「li512e4:teste」は、[512,test]
辞書
「d5:leveli13e5magic6halitoe」は {level:13,magic:halito}

Bencoding実装

• Bencodingはパースしやすい構造
• BNFから機械的にコードを抽出

見慣れたデータ構造に落とす

Dart言語には、Bencoding のデータ構造をもっています。今回は、Bencdoingのデータを読み込み、Dart言語のデータ構造に落とこみます。
Bencodeの文字列は、Dart言語ではcore.Stringで表せます。Bencodeの数字は、Dart言語では、core.int で表せます。 Bencodeのリストは Dart言語のcore.List、Bencodeの辞書は、Dart言語ではMapで表現できます。

Bencodeはパースしやすい構造

Bencode はパースが容易な構造になっています。なぜならば、どのデータなのかが、最初の一文字目で判別する事ができるからです。
“i” ならば、整数。 “0-9” ならば、文字列、”l” ならばリスト、”d” ならば辞書 といった感じです。
これを、コードに直すと、以下のような感じになります。

例

  Object decodeBenObject(data.Uint8List buffer)  { 
    if( 0x30 <= buffer[index] && buffer[index]<=0x39) {//0-9
      return decodeBytes(buffer);
    } else if(0x69 == buffer[index]) {// i 
      return decodeNumber(buffer);
    } else if(0x6c == buffer[index]) {// l
      return decodeList(buffer);
    } else if(0x64 == buffer[index]) {// d
      return decodeDiction(buffer);
    }
    throw new ParseError("benobject", buffer, index);
  }

見ての通り、先頭の値に応じて処理が分岐しているだけです。後は、おのおのデータ構造とみなして、変換してあげれば完成です。

BNF から機械的にパーサーを書く

BNFで書かれた構文は機械的にパーサーを書く事ができます。

• 規則名をメソッドにする。
• ルールに文字列がでてきた場合、一致するかチェックする
  ルールに規則がでてきた場合、そのメソッドを呼び出す
• ルールに違反する場合は、Exception をスローする。

プログラム言語、自然言語といったものは、もう少し工夫が必要ですが、今回の対象は、基本的なルールを守るだけで実装できます。もう少し詳細な情報が欲しい場合は、「Language Implementation Patterns 」という本を読む事をお勧めです。
具体的に、Bencode 用のパーサーを作成しながら、見ていきましょう。
例えば、Dictionary は以下のように書けます。

例

  Map decodeDiction(data.Uint8List buffer) {
    Map ret = new Map();
    if(buffer[index++] != 0x64) {
      throw new ParseError("bendiction", buffer, index);
    }

    ret = decodeDictionElements(buffer);

    if(buffer[index++] != 0x65) {
      throw new ParseError("bendiction", buffer, index);
    }
    return ret;
  }

BNFと一対一の関係がある事が解ると思います。Dictionary は「 “d” bendictionelements “e”」と文法で表現されます。ですから、”d”という文字か確認。　dictionelements のメソッドを呼び出す。“e”という文字か確認する。　ルール通りです。

テストを書く

テストを書きながら、パーサーを書いていきましょう。まずは整数からです。

例

   unit.test("bencode: number", () {
      num ret = hetima.Bencode.decode(toBuffer("i1024e"));
      unit.expect(1024, ret);
  });

このテストを満たすように、パーサーを書きます。bencodingで整数は、 「“i” *(0-9) “e”」と書けます。なので、これもルールに従って以下のように書けます。

例

 num decodeNumber(data.Uint8List buffer)  {
    if(buffer[index++] != 0x69) {
      throw new ParseError("bennumber", buffer, index);
    }
    int returnValue = 0;
    while(index<buffer.length && buffer[index] != 0x65) {
      if(!(0x30 <= buffer[index] && buffer[index]<=0x39)) {
        throw new ParseError("bennumber", buffer, index);
      }
      returnValue = returnValue*10+(buffer[index++]-0x30);
    }
    if(buffer[index++] != 0x65) {
      throw new ParseError("bennumber", buffer, index);
    }
    return returnValue;
  }

数字を取り出す部分が少し複雑ですが、無事テストが通るコードがかけました。この調子で、文字列、リスト、と同じようにテストしながら、作成すれば完成です。kyorohiroが作成した物は、以下にあります。「https://github.com/kyorohiro/dart_hetimalib」 事の顛末を知りたい方は参照してください。

Bencodeデータを作成する

;;;;Dart言語のオブジェクトを Bencode に変換してみましょう。パーサーを作成した時と同様に、Dart言語の「Map,List, string, int」をBencodeの「Dictionary, List, String, Number」へ変換していきます。
パーサーを書いた時と同じように、BNFで書かれた構文は機械的に書けます。

• 規則名をメソッドにする。
• ルールに文字列がでてきた場合、文字列を追加する
• ルールに規則がでてきた場合、そのメソッドを呼び出す

まずは、各データの種類に応じて、各規則を処理するメソッドへ処理を渡します。

例

   void encodeObject(Object obj) {
    if(obj is num) {
      encodeNumber(obj);
    } else if(obj is String) {
      encodeString(obj);    
    } else if(obj is List) {
      encodeList(obj);
    } else if(obj is Map) {
      encodeDictionary(obj);
    }
  }

といった感じで書けます。後は、型に応じて、文法に従って変換していけば完成です。
例えば、Dart言語のint型 を Bencodeの Number へ変換する方法は以下のような感じにかけます。

例

   void encodeNumber(num num) {
    builder.appendString("i"+num.toString()+"e");
  }

”i” 、値、”e” の順でデータを結合します。ルール通りです。例えば、Dart言語のList型を、Bencode のList へ変換する方法は以下の通りです。

例

  void encodeList(List list) {
    builder.appendString("l");
    for(int i=0;i<list.length;i++) {
      encodeObject(list[i]);
    }
    builder.appendString("e");
  }

“l” 、Objectを変換するメソッド、”e” の順でデータを結合します。このように、BNFで記載した文法の通り、規則名をメソッドを渡することで実現できます。

テストを書く

後は、テストを書きながら、完成させましょう。例えば、Numberのテストは以下のような感じでかけます。

例

   unit.test("bencode: number", () {
      Uint8List ret = hetima.Bencode.encode(1024));
      unit.expect(UTF.encode(ret), “i1024e”);
  });

テストを書いている時に、仕様の考慮漏れが見つかることがあります。今回の場合でも、実際にテストしたことで考慮漏れがあることがわかりました。 以下のようなコードを書くと、テストがFailedします。

例

   unit.test("bencode: uint8list", () {
      Uint8List input = new Uint8List(1);
      input[0] = 0x61;//a
      Uint8List ret = hetima.Bencode.encode(1024));
      unit.expect(UTF.encode(ret), “2:a”);
  });

Bencodeでは、byte配列もStringで扱うのでした。今回、Byte配列は考慮できていませんでした。
この調子で、String, List, Dictionary の順で作成していけば完成するはずです。

Torrent ファイルの中身

• TorrentファイルはBencodingで記載されている
• Trackerのアドレスが記載されている
• ファイル名が記載されている
• ブロックデータごとのSHA1 Hashが記載されている

Torentファイルを読み込んでみよう

無事、Bencodeのパーサーを書く事ができました。これで、Torrentファイルの中身を解析できます。Torrentファイルの中身を確認してみましょう。
さっそく、Torrentファイルを読み込んでみましょう。Parserを作成していない方は、「https://github.com/kyorohiro/dart_hetimalib_test/tree/master/hetimalib_sample/TorrentFileParser」を利用してください。
読み込んで見ると以下のようなデータ構成である事がわかります。

例

{
   "announce":http://example.com/tracker,
   "created by":torrent generator,
   "creation date":1364723642,
   "encoding":utf-8,
   "info":{
      "length":1024,
      "name":xxx
      "piece length":16384,
      "pieces":<......20バイト単位のバイナリデータ>
   }
}

announce

Tracker サーバーのアドレスが記載されています。本アドレスのサーバー
にからデータを配信してくれる端末を紹介してもらえます。

created by

本ファイル生成したツールを示す名前のようです。

creation date

本ファイルが生成された日にちを表しているようです。

info.length

配信されているデータのサイズです。1024byte のデータである事がわかります。

info.name

配信されているデータのファイル名です。xxx という名前である事が解ります。

piece length

データを配信する際に、分割するサイズです。16kb単位で分割する事がわかります。

pieces

分割されたデータごとのHash値です。データーの正当性を判定するのに使用します。

ファイルが複数の場合

ひとつのファイルを配信するデータは説明した通りです。複数のファイルをパッケージする場合は、もう少し構造が複雑になります。

例

{
   "announce":http://example.com/tracker,
   "created by":torrent generator,
   "creation date":1364723642,
   "encoding":utf-8,
   "info":{
      “files”: [
           {
               length:512,
               path:[aaa, bbb.mp3]
           },
           {
               length:1024,
               path:[ccc, ddd.mp3]
           },
       ]
      "name":xxx
      "piece length":16384,
      "pieces":<......20バイト単位のバイナリデータ>
   }
}

さきほどのと比較すると、info辞書の中に、files リストが増えています。今回の場合だと、「xxx/aaa/bbb.mp3」、「xxx/ccc/ddd.mp3」という2つのデータが含まれている事が読み取れます。

Torrentファイルを作成してみよう

これらの理解できた事を整理して、理解出来ていない事を発見しながら、Torrentファイルを作成するツールを作成してみましょう。無事作成できたならば、だいたいは理解できたという事になります。既に、Bencoding のパーサーはありますから、ゴールは目の前です。

例

{
      Map file = {};
      Map info = {};
      file[TorrentFile.KEY_ANNOUNCE] = announce;
      file[TorrentFile.KEY_INFO] = info;
      info[TorrentFile.KEY_NAME] = name;
      info[TorrentFile.KEY_PIECE_LENGTH] = piececSize;
      info[TorrentFile.KEY_LENGTH] = targetLength;
      info[TorrentFile.KEY_PIECE] = pieceBuffer;
      Bencode.encode(file);
}

といった感じで、必要な情報をMapに配置して、Bencode にエンコードすれば完成です。

実際に作成してみると、明らかでなかった点が現れてきます。例えば、ファイルが複数ある場合は、pieceデータをどのように算出するのでしょうか？ まだ、明らかになっていませんでした。2つ生成する方法を思いつきました。どちらかが、Torrentで採用されている方法だと良いのですが..。

1. ファイル単位で、pieceデータを作成する。
2. 複数ファイルは結合してひとつのファイルと見なしてから、pieceデータを作成する。

実際に試してみたところ、 2の方法が採用されているようです。具体的には、

例

{
        Blob fileA =...
        Blob fileB =...
        Blob image = new Blob([fileA, fileB]);
        FileReader reader = new FileReader();
        reader.readAsArrayBuffer(image).then((e){
             int start = 0;
             do {
                int end = start+pieceLength;
                if(end<image.size()){ end = image.size()}
                crypto.SHA1 sha1 = new crypto.SHA1();
                sha1.add(reader.sublist(start,pieceLength));
                print(sha1.close().toList().toString());
                start = end;
            } while(end < image.size()):
        });
}

といったコードで生成できます。

サンプル実装

• https://chrome.google.com/webstore/detail/hetimatorrentfilesample/aponagendffongjcpfmloabmbilnapoo

• https://github.com/kyorohiro/HetimaTorrentFile