FPGA開発日記

FPGAというより、コンピュータアーキテクチャかもね! カテゴリ別記事インデックス https://sites.google.com/site/fpgadevelopindex/

Protocol Bufferとは何なのか(3. シリアライズ化のためのアルゴリズム)

f:id:msyksphinz:20160723175322p:plain

msyksphinz.hatenablog.com

msyksphinz.hatenablog.com

Protocol Bufferの使い方は何となく分かったが、途中で生成されるバイナリファイルの仕組みについて良く分かっていない。 圧縮してあるのかと思いきや、そんな訳でもない。そこまで圧縮率は高く無いし、いったいどのような仕組みでシリアライズ化が行なわれているんだろう?

調査してみると、GoogleのProtocol Bufferの解説ページに基礎アルゴリズムの解説が載っていた。

Encoding  |  Protocol Buffers  |  Google Developers

プロトコルバッファのシラアライズ化の仕組み

プロトコルバッファのシリアライズ化では、バイト単位に変換が実行される。このとき、

  1. Variant(メッセージの型)を決めるヘッダ
  2. データ本体

に分かれており、データ本体をどのように構成するかというのが重要になる。データはバイト単位で分割されており、最上位ビット(MSB)は特別な意味を持つものになっている。 つまり、逆に言えば各バイトで意味を持つのは下位の7ビットのみとなる。 最上位ビットは、メッセージ内で次に続くバイトが存在しているかを示している。つまり1ならば次のバイトも同一メッセージで、0ならばこのバイトでメッセージのグループは終了。

例えば、ここに300(10進数)という数値があったとしよう。これは以下のようにしてシリアライズ化される。

  1. 300 = 0x12c = 0b1_0010_1100
  2. 下のバイトから順に見ていく。下位から7ビットは010_1100であり、次にバイトが続いていくので、最上位に1が付き、先頭のバイトは0b1010_1100となる。
  3. 次の7ビットは0b10であり、これでデータは終了である。従ってMSBには0が付き、データは0b0000_0010となる。

これに、さらにデータの情報を持つヘッダを付ける。ヘッダの付け方は、"Message Structure"を参照してほしいが、https://developers.google.com/protocol-buffers/docs/encoding から抜粋すると、

f:id:msyksphinz:20160729013804p:plain

従って64ビット以下の整数ならば先頭に0b0000_0000を付加する。これで、最終的なデータは0b0000_0000_1010_1100_0000_0010 となる。

これ、いまいち利点が分からないのだが、高速にエンコーディングできる、という話だけなんだろうか?データ量の圧縮には少なくとも無意味だ。 そうするとシリアライズの速度に利点があるとしか思えないが、それにしてもビットシフトの必要があったりだとか、計算量的にもあまり美味しくないと思うのだがどうなんだろうか。