P2P探訪 Raider その1-2 Torrentファイルフォーマット

というわけで、前回に引き続いて、この記事ではTorrentファイルについて説明します。


[Torrent file format]
前回、Bencodingを実装したのでTorremt Fileを読み込めることができるようになりました。
今回は、Torrentファイルから必要な情報を読み込む方法について解説します。

torretファイルから取得できる情報はどんなものかは、別の機会に解説します。
ここでは、torrentファイルには 2つのフォーマットがあることとデータ構造を説明します。
たとえば、「"announce"というデータが何なのか？」については解説しません。


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

ひとつの時を、「single file」 複数の時を「multi 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"

といった感じです。
multi file の時は、filesというDictionが追加されるわけです。


[reference]
- 成果物 torrent file
  https://github.com/kyorohiro/Raider/tree/master/Raider/src/info/kyorohiro/raider/util/torrent
  
- Torrent spec
  http://en.wikipedia.org/wiki/Torrent_file
  http://www.bittorrent.org/beps/bep_0003.html
  http://sourceforge.net/projects/bittorrent/
 

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
  

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
  

KyoroText で使用されている技術 その11

[課題] Terminalっぽいことを、してみたい。

私はxyzzyというEditorを愛用しています。xyzzyには、Editorからshellを操作する機能があります。
「KyoroTextにも、Shellモードが欲しいなぁ～」と考えていました。

ためしに実装してみたら、そこそこ動いたので簡単に紹介します。


[問題]
 Googleを多様して、以下のような問題を解決できました。
 -A Androidで、CLIアプリを動作させめ方法は？
 -B cd した後の、現在参照しているフォルダを利用したい？


[A] Androidで、CLIアプリを動作させる方法は？
 自分以外のAndroidアプリを起動する場合、通常は、Intentを使用します。
「cd」「ls」dateといった。/system/bin配下にあるネイティブアプリを動作させるには、
 どうすれば良いのでしょうか？ Intentで実現できるのでしょうか？

 Runtimeクラス、ProcessBuilderクラスで実現できます。
 細かな使い方は、Google先生に聞くと良いでしょう。

 KyoroTextでは、以下のようなコードを書きました。
 https://github.com/kyorohiro/KyoroHelloAndroid/tree/master/KyoroCommon/src/info/kyorohiro/helloworld/util/shell
 CLIAppKicker

>
>   CLIAppKicker#start(String command)
>
startを呼ぶとCLIアプリを起動します。


 [B] cd した後の、現在参照しているフォルダを利用したい？

「Aの問題」が解決しました。なので、「ls」使いたい時は、「CLIAppKicker#start("ls")」
 とすれば、「ls」が呼べます。

 しかし、うまくいかない場合があります。
「cd」です。

 以下のようなシナリオを考えてみましょう。
  1. "/" にいる。
  2. cd mnt とする。
  3. cd sdcard
 として、SDカード配下に移動したいとする。

  1. CLIAppKicker#start("cd mnt")
  2. CLIAppKicker#start("cd sdcard")
 のようなコードで実現できそうです。しかし、
 子プロセスの情報は引き継がれません。

  1. CLIAppKicker#start("cd mnt")
  ---> /mntい移動する。
  2. CLIAppKicker#start("cd sdcard")
  --> /sdcardに移動する。
 となり、思い通りの場所(/mnt/sdcard)に移動できません。




 この問題は、CLIAppKicker#start("sh") とすることで解決できます。
 KyoroTextでは、以下のようなコードを書きました。
 https://github.com/kyorohiro/KyoroHelloAndroid/tree/master/KyoroCommon/src/info/kyorohiro/helloworld/util/shell
 CmdSession.java




[気をつけた点]
 topコマンドなど、プロセスが動作し続けるアプリでは、「InputStream#available() == 0」の状態で、InputStream#read()すると、次へ進まなくります。データが入力されるまで待機するためです。
なので、必ず、「InputStream#available() > 0」ことを確認してから、InputStream#read()する
ようにしました。



[次回]
テスト自動化はできた!!どのくらいテストできたか定量的に客観的にしりたい!!
どうすればよいでしょうか？
次回はEMMAというテストカバレッジツールを使用する方法について解説します。

KyoroText で使用されている技術 その10

[課題] File#listFiles(FileFilter filter) を中断できるようにしたい

KyoroTextはテキストビューアなので、ファイルシステムからテキストファイルを選択して、開く機能が必要です。

解決すべきシナリオは、
アプリ  : 1. ファイルシステム上のファイルの一覧を表示する。
ユーザー: 2. ファイルまたはフォルダーを選択する。
アプリ  : 3. 選択されたものがファイルならば、テキストとして表示する。フォルダならば、1に戻る。
といった感じでとても単純です。

しかし、ちょっとした罠があります。それは、「一覧表示すべきファイルの数: 0～無限」ということです。
大量のファイルを表示する場合、以下の問題が発生します。
[A] 一覧を出すのに時間がかかる。 
[B] 一覧表示すべきファイルの数は、ヒープに収まらないこともありえる。

たとえば、[A]については、端末起動直後などに10000件程度のファイル一覧を取得する場合、10秒以上待たされる場合もありました。
つまり、Thread#interrupt()が呼ばれても、最悪10秒以上は処理を返さないことがあるということです。


 [Androidの作り] 
// 
// 実際のコードです。
//
    public File[] listFiles(FileFilter filter) {
        File[] files = listFiles();
        if (filter == null || files == null) {
            return files;
        }
        List result = new ArrayList(files.length);
        for (File file : files) {
            if (filter.accept(file)) {
                result.add(file);
            }
        }
        return result.toArray(new File[result.size()]);
    }

[A]、[B] の各々はJava側では解決する方法はなさそうですね!!


 [KyoroTextの解決方法] 

[A]に時間がかかることはあきらめて、中断できる機能を追加することにしました。

1. File#listFiesの呼び出す時は、専用のスレットを呼び出す。
2. 1の処理が終わるまで待つ。
3. もしも、Thread#interruptが呼ばれたら、File#listFilesの処理が終わるのを待つのをやめる。

具体的には、以下のような機能を用意しました。

#AsyncronousTaskクラス

　AsyncronousTask atask = new AsyncronousTask#AsyncronousTask(Runnable 作業完了を監視したいタスク)
  Thread runner = new Thread(atask);
  runner.start();
  if(atask.syncTask()) {
     // タスクが完了した。
  } else {
     // interruptされた
  }

https://github.com/kyorohiro/KyoroHelloAndroid/blob/master/KyoroCommon/src/info/kyorohiro/helloworld/util/AsyncronousTask.java

https://github.com/kyorohiro/KyoroHelloAndroid/blob/master/KyoroCommon/src/info/kyorohiro/helloworld/util/FileListGetter.java

 [PS] 

次回、今回のAsyncronousTaskを使用する方法だと、使用する側は、AsyncronousTaskと監視対象の両方のクラスを制御しなくてはならない。これを一つにまとめると、使いやすさがUPします。
KyoroTextでおこなった方法について説明します。

キーワードは、Future Task 

KyoroText で使用されている技術 その9

InputConnectionの使い方の説明は、家に帰って動作確認しながらでないと、
記事が書けないようです。
家に帰ったら、別の事がしたなって、全然ブログま更新ができていませんでした。

InputConnectionの使い方の説明が終わるまでは、次には進まないぞ!!と考えていましたが、
やめました。

※ 通勤中に電車の中で書けるような事でないとダメみたい。


[課題] 走らせるスレッドを制限したい その1

同時に複数のスレッドごりごり走ると、低性能な端末だとダメダメな感じです。
なので、スレッド数をある程度管理化におく必要があります。
なおかつ、あまり、作業を作る側は、管理している側を意識したくない。


[KyoroTextでの解決]
  同時にひとつだけ、Threadが動く事を保障したクラスを用意しておいて。
  作業(Runnable)をそのクラスに渡す。

[パターン]
 いくつかパターンがあります。例えば、
- 1  指定された作業をキューにつんで置いて、順番にアクセスする。
- 2  作業が指定されたら、他の作業をすべて殺して、その作業を優先する。
- 3  等々

今回は、-2をとりました。

[作り]
 使う側は、とりあえず、以下のメソッドに依頼したい作業を指定するだけ。
  SingleTaskRunner#start(Runnable task)

 管理側
  1. 動作中のThreadを中断する。
  2. joinして、Threadが終了するのを待つ
  3. 新しい作業を開始する。
 
 ちょっと工夫した点は、1.、2、3 の作業を、別スレッドで行うようにしたところ。
 このstartメソッドを呼び出した側がロックを開放しないと、今動作中のThreadが終了しない
 といった事がおきると困のます。なので、別スレッドにしておくほうが安全です。
※ 工夫したというよりは、上記が理由で、KyoroTextにて、デットロックを起こしてしまったので、直したという表現がただしい。

[中身] 
 https://github.com/kyorohiro/KyoroHelloAndroid/blob/master/KyoroCommon/src/info/kyorohiro/helloworld/util/SingleTaskRunner.java


[次回のネタ]
- データ保存操作だとかを、バックグラウンドで実施したい。しかし、バックグラウンドへ移動すると、PFから、プロセスキルされる可能性が高くなります。(※例えServiceと動作していても)
  KyoroTextでの、プロセスキルへの対策を説明します。
  キーワードは、 low memory killer,  taskmanager, process kill

KyoroText で使用されている技術 その8

その7の続き...


[小課題] SurfaceViewでEditorを作る。その1 
- 未確定文字と確定文字について


 確定文字と未確定文字の扱いについて説明します。

 日本語を入力する場合、一旦、「ひらがな」を入力した後で、「漢字」に変換します。この変換される前の状態を
「未確定文字」、変換後の状態を「確定文字」と呼ぶことにします。

 例えば、「お腹が空いた」と入力したい場合、
 1. 「おなかがすいた」と未確定文字を入力
 2. 「お腹が空いた」と確定文字に変換
 となります。


 APIの流れを見てみましょう。
   1. IMEアプリ : フォーカスがあるViewから、InputConnectionを取得する。
   2. IMEアプリ : InputConnection#setComposingText("おなかがすいた", 1);
   3. Editor    : 未確定文字をユーザーに表示
   4. IMEアプリ : InputConnection#inputCommitText("お腹が空いた", 1);
   5. Editor    : 確定文字として、テキストを更新


[サンプル]
 - 上記シナリオをInstrumentationで記載しました。ログを仕込めば、APIの流れがわかります。
  https://github.com/kyorohiro/KyoroSamples/blob/master/KyoroSampleSurfaceViewEditor/src/info/kyorohiro/samples/android/test/CheckForComposingText.java



[PS]

 -  setComposingText()、inputCommitText() で渡されるテキストについて 
  setComposingText()、inputCommitText() で渡されるテキストはCharSequenceです。
  Spannable装飾ありのテキストが渡さることがあります。

  例えば、「<|>」をカーソルとします。「おなかがすいた」と入力した後で、
 「おなか」だけを変換したい場合、以下のようなシナリオになります。
　1.「おなかがすいた<|>」と入力
  2.「おなか<|>がすいた」と移動
  3.「お腹<|>がすいた」と変換
  4.「お腹がすいた<|>」と確定する。

  ほとんどの場合、この時のカーソル位置は、Editor側のカーソルではありません。
  IMEのものです。装飾ありのテキストを使用して表現されます。
  例えば、  「おなか<|>がすいた」は、「おなか」の部分の背景色をグレーにするとかしています。

  ※ このような変換処理は、IMEアプリ側がやってくれるわけですが、
     Editor側は、装飾情報を解析して、ユーザーに表示してあげる必要があります。


 -  setComposingText()、inputCommitText() で渡されるnewCursorPositionについて
Editor側のカーソル位置を表しています。
 * 0 の時、「<|>お腹がすいた」
 * 1 の時、「お腹がすいた<|>」

となります。