PNGを端末に表示するプログラムをRustで書いた

PNGを端末に表示するプログラムを作りました。

github.com

使い方

cargo run /Path/to/Windows_logo.png

とすると、👇のように端末に画像が表示されます。透過画像も表示できます。

ちなみに、PNGの画像形式は何パターンかあるのですが、そのすべてに対応してるわけではないので、表示できない画像もあります。あしからず。

メイキング

PNGの規格が理解できたら、あとは流れで作れると思うので、PNGの規格を理解しましょう。 PNGの規格はRFCで公開されているので、それを読んでください。

...というわけにも行かないので、解説記事を読んで下さい 👇

dawn.hateblo.jp

とはいえ、RFCの英語は簡単だし読みやすいので、読むのもそこまで大変ではないと思います。

なぜやったのか

mixiインターン期間中に開催された「インターン生vs社員LT大会」で、インターン生の人がzip圧縮に関する発表をしていました。その人は、zipの規格を読んでそれを元にzip圧縮するソフトをC++で実装したそうです。
なんでわざわざC++でやったんですか?とその人に聞いたところ、バイト列の扱いがLLなどに比べてやりやすいからだという返事が返ってきました。

なるほどな〜やっぱり人間はC++を書かなきゃいけないんやな〜ってその時は思ったんですが、インターンが終わるぐらいのときに、Rustはそういう低レイヤーなものを書くのに向いているのではないか、と思うようになりました。

そういうお気持ちだったときに、「ディジタル情報処理」という授業の先生が「ディジタル情報処理に関係するプログラム書いたら単位出すで」と言っていたので、いっちょうやったるかという機運が高まり、プログラムが作成されました*1*2

Rustに関する感想

バイト列の取り扱いはいい感じだった

結論から言うと、Rustでバイト列を取り扱うのは結構やりやすいです*3

例えば、u8の配列から4つづつ読み出して、u32と見做して値を取得したいというような課題があるわけです。 そういうとき、Rustにはbyteorderというcrateがあって、👇のようにして数値に変換できます。

extern crate byteorder;
use byteorder::{BigEndian, ReadBytesExt};

fn main() {
    let bytes: Vec<u8> = vec![0,0,1,1, 0,0,1,2];

    println!("{}", (&bytes[0..4]).read_u32::<BigEndian>().unwrap()); // => 257
    println!("{}", (&bytes[4..8]).read_u32::<BigEndian>().unwrap()); // => 258
}

こういうcrateがあって、そこそこ人気がある(githubで200スターぐらい)っていうことは、低レイヤーな処理をRustにやらせたいという需要はやはり一定あるのかな、と感じます。

他にも、Rustにはプリミティブな数値型がたくさんあって、用途に応じて使い分けられるのは良いと思いました。

また、オーバーフローが起きたときにエラーを出してくれるのですが、各数値型にはwrapping_addのようなメソッドが生えておりまして、このメソッドを通して計算をすると、オーバーフローが起こったときにスルーしてくれます。こういうのが明示的に書けるのは良いですね。

fn main() {
  let a: u8 = 200;
  let b: u8 = 200;
  
  let c: u8 = a + b;             // => panic!
  let c: u8 = a.wrapping_add(b); // => 144
}

Rustの学習コストはやっぱり高い

一方で、やはりRustの学習コストは高いなぁと思いました。 僕自身はライフタイムや型システムを(一応)理解しているので、謎のコンパイルエラーに悩まされるという初心者あるある現象が発生することはなかったですが、moveを避けるために.clone()を乱発するコードになってしまい、メモリをうまく使えていないなあという気持ちになりました。

まとめ

車輪の再発明を通して学んでいきたい。

github.com

*1:ちなみにこのプログラムを先生に見せたら「ディジタル情報処理に関係してるかっていうと微妙だねぇ」という返答が返ってきました。先生的には離散フーリエ変換とかしてほしかったみたいです。

*2:エッジの検出してAAに変換するとかすれば、ディジタル情報処理とみなせると言われました。次の課題はこれです。

*3:僕はバイト列をゴニョゴニョするようなことは普段やらないし、ましてやC++なんて書いたこともないので、あくまで「LLに比べて」やりやすいということです

PNGの規格を簡単に説明する

PNGの規格を勉強する機会があったので、その内容を簡単に説明します*1

PNGはいくつかの"チャンク"が集まって構成されています。例えば、IHDRチャンクやIDATチャンク、PLTEチャンクなどがあります。では、PNGファイルという単なるバイト列から、どのようにチャンクを抽出すれば良いのでしょうか?

これは、PNGファイルの構造を知ることでわかります。

PNGファイルの構造

PNGファイルの構造は、以下のようになっています:

  • ファイル先頭の8byteは 必ず 137, 80, 78, 71, 13, 10, 26, 10である
    • PNGファイルであることを識別するため
  • それ以降のバイト列は、次の構造の繰り返しである
    • 先頭の4byteは、チャンクのサイズを表す(Length)
    • 次の4byteは、チャンクの種類を表す(Chunk Type)
      • 例えばIHDRとかIDATとかPLTEになったりする
    • 次のnbyteは、チャンクのデータを表す(Chunk Data)
      • nはLengthの値
    • 次の4byteは、CRCを表す(CRC)
      • いわゆる誤り検出のためのデータ

この構造に従ってPNGファイルをパースすると、複数のチャンクを取りだすことができます。
あとはこれらのチャンクを画像として解釈すればいっちょう上がりというわけです。

重要なチャンク

画像データを取得するために必須のチャンクについて解説します。

IHDRチャンク

まず、チャンクの中から、IHDRチャンクを探してきましょう。こいつはいわゆるヘッダーです。
Width, Height, Color Typeの3つのデータが含まれています*2

このColor Typeというのが何を表しているのかというと、

  • "パレット"を使っているか
  • 白黒画像なのか、カラー画像なのか
  • アルファチャンネルが使用されているか(透過画像かどうか)

という3つの情報を表しています。

PLTEチャンク

Color Typeを見て、"パレット"が使われているというのであれば、必ずPLTEチャンクが存在します。

このPLTEチャンクというのは、「画像内で使われ得るすべての色」の情報を持っています。 例えば、赤一色の画像であればrgb = [255,0,0]という値だけを持ちますし、赤と白の二色だけの画像であればrgb = [255, 0, 0]に加えてrgb = [255,255,255]という値も持ちます。また、アルファチャンネルが使用されている場合は、RGBの三色に加えてもう一つ「透過度」を表すbyteが存在します。例えば、「赤色で全く透明ではない色」は[255, 0, 0, 255]になるわけですね。

PLTEチャンクのバイト列から色情報を取得するのは簡単で、RGBなら3つづつ(RGB+αなら4つづつ)先頭のバイトからグループ化していけば良いです。


なんでこんなものが存在するのかというと、その方が画像のサイズを落とせるからです。例えば、3色しか使われない画像を圧縮するとき、すべてのピクセルごとに色情報を持つのは容量の無駄です。
それよりも、その3色にそれぞれ番号を振っておいて、「このピクセルはn番の色、このピクセルはm番の色、このピクセルは...」というようにデータを持っておくほうが、使う色が少ない場合は容量が少なくて済みます。

IDATチャンク

ここが画像データの本体です。IDATチャンクには、実際の画像データが格納されています*3

IDATチャンクに格納されている画像データはDeflate圧縮されています。そのため、IDATチャンクから画像データを取得するためには展開する必要があります*4。展開されたデータは、👇のように、左上から右下に向かって1ピクセルづつ色の情報が並んでいます*5

f:id:threetea0407:20171022184226p:plain

画像データを取得する

ここまでのチャンクを解釈して画像データを取得するわけですが、結構複雑です。

"パレット"を使用する場合

この場合は簡単で、画像データを1byteづつ読んで、その値を「パレットのインデックス」として解釈します。

例えば、PLTEのデータがRGBs = [[255, 0, 0], [0, 255, 0], [0, 0, 255]]であり、IDATのデータがpixels = [0, 1, 2, 0, 1, 2]であれば、画像の色データはcolors = [[255, 0, 0], [0, 255, 0], [0, 0, 255], [255, 0, 0], [0, 255, 0], [0, 0, 255]]になるということです*6

"パレット"を使用しない場合

この場合は、IDATのデータを直接解釈します。ここが結構複雑です。

まず、IDATのバイト列をHeightの数に分割します。例えば、Heightが100pixelの画像であれば、100個の等しい長さのバイト列に分割するわけです。
そして、ここがややこしいのですが、各バイト列の先頭1byteはfilter methodを表しています。従って、色情報そのものは2byte目から始まるわけです。

filter methodRFCにおいて定義されておりNone, Sub, Up, Average, Paethの5種類があるのですが、一番単純なNoneについてはPLTEチャンクを解釈したときと全く同様に解釈すれば良いです。つまり、2バイト目から3byteづつ(αチャンネルがあるときは4byteづつ)グループにしてしまえば、それぞれのグループが1つのピクセルを表すことになります。簡単ですね。

ところで、filter methodは各行ごとに設定されています。従って、各行ごとに違うfilter methodを使うということができます。
実際に、Portable Network Graphics - Wikipediaにデモ画像として掲載されているサイコロの画像(👇)は、行ごとに異なるfilter methodが設定されているようです。

まとめ

PNGファイルの規格の説明は以上です。
あとはプログラムを書けば、実際のPNGファイルを解釈することができます。

*1:PNGの規格自体はRFC公開されている

*2:本当はもっとある

*3: IDATチャンクは1つのファイルに2つ以上含まれることがあります。これは、チャンクの長さに制限がある一方で、画像データのサイズには制限がないからです。

*4:Deflateのアルゴリズムに関してはこの記事の解説すべき範囲を外れるので特に解説しないが、実際にはDeflateを取り扱うライブラリが多くの言語で用意されているのでそれに突っ込めば良い。

*5:インターレースとかが出てくると例外はあります

*6:従って、IDATに含まれる各byteの値は、PLTEのデータの長さを超えることはありません。

機能追加と同時にリファクタリングをしてもいいか

「機能追加と同時にリファクタリングをしてもいい」という記事がはてブに上がっていたので、思うところを述べる。

scrapbox.io

結論

問題意識

機能追加をするときにリファクタは避けられない。既存の処理を共通化して再利用して機能を追加した方が効率的だからである。

しかし、機能追加とリファクタが混ざったPRを出すのはダメだ。なぜなら、リファクタによって機能が失われていないかどうか確認するのが面倒になるからだ。

解決策

では、どうすればよいのか?

開発中はリファクタと機能追加を平行して行い、リファクタと機能追加のPull Requestを別々に出せば良いのである。

手順

この解決策を実行するには以下のようにする:

  1. 開発中はリファクタと機能追加を同時並行で行い、適宜コミットする。
  2. PRを作成する前にgit rebase -iコミットを入れ替え 、「リファクタのみのブランチ」と「機能追加のみのブランチ」を作成する。
  3. それぞれのブランチについてPull Requestを作成する。
  4. レビュアーは、「リファクタのみのブランチ」をレビュー&マージした後に、「機能追加のみのブランチ」のレビューを行う。

つまり、開発完了時の

* implement B <-- some_new_feature
*  refactor Y
* implement A
*  refactor X
*        base

という歴史を、

* implement B <-- some_new_feature
* implement A
*  refactor Y <-- refactor_for_new_feature
*  refactor X
*        base

のように書き換え、2つのPull Requestを作成するのである。

このようにすれば、「機能追加とリファクタは同時にやりたい」という欲求と、「機能追加とリファクタは別にレビューしたい」という欲求を両立させることができる。

元記事に対する感想

「リファクタと機能実装を分けると、リファクタの方のPRでは「設計が壊れ」ているコードをレビューしなければいけないので良くない」みたいな記述があったが、ちゃんと意味のあるリファクタであれば、それはそれとして独立した一つのPRになると思う。「リファクタのPRは『設計が壊れ』ている」ことは、変なリファクタをしてるからなのではないかと思う。

また、「githubのクソUIのせいで、リファクタと機能実装が混ぜ込まれたPRがレビューしづらい」という意味の記述があったが、ほならねとしか言えない。そもそもdiffを出してるのは、変更範囲だけを見たいという欲求があるからであって、「全体を見てもらえばもっとわかりやすいんです!!!」というのはレビュワーに対する負荷を増やすだけだ。

iter()とinto_iter()の違いを整理した

VectorIteratorに変換する時にいつも混乱していたので整理した。

混乱

あるVectorの要素すべてを3倍するコードを考える。

fn main() {
    let vec1 = vec![1,2,3,4,5];
    let vec2 = vec1.iter()
                   .map(|i| i * 3)
                   .collect::<Vec<i32>>();

    println!("{:?}", vec1);
    println!("{:?}", vec2);
}

このコードはコンパイルできるが、以下のような疑問がある。

  1. 5行目で vec1はなぜ使えるのか? 3行目の vec1.iter()で使われているじゃないか!
  2. map(|i| i * 3)iは参照なのか値なのか?

これらの疑問に関する答えは、

  1. iter()Vectorをmoveしない。into_iter()Vectorをmoveする。
  2. iter()Vectorから「参照のコレクションであるIterator」を作成し、into_iter()Vectorから「値のコレクションであるIterator」を作成する。

ということになる。

into_iter()の挙動

呼び出し元のVectorの所有権

fn main() {
    let vec1 = vec![1,2,3,4,5];
    let vec2 = vec1.into_iter()
                   .map(|i| i * 3)
                   .collect::<Vec<i32>>();

    println!("{:?}", vec1); // Error!
}

このコードはコンパイルできない。というのも、3行目の into_iter()vec1をmoveするからである。

このように、 into_iter()は、呼び出し元のVectorをmoveする。

mapに渡される要素は参照なのか?

fn main() {
    let vec1 = vec![1,2,3,4,5];
    let vec2 = vec1.into_iter()
                   .map(|i| *i * 3) // Error!
                   .collect::<Vec<i32>>();
}

このコードはコンパイルできない。というのも、4行目の map(|i| *i * 3)iは、参照ではなく値だからである。

このように、into_iter()に連なる mapには、参照ではなくが渡される。

iter()の挙動

呼び出し元のVectorの所有権

fn main() {
    let vec1 = vec![1,2,3,4,5];
    let vec2 = vec1.iter()
                   .map(|i| i * 3)
                   .collect::<Vec<i32>>();

    println!("{:?}", vec1); // OK!
}

このコードはコンパイルできる。iter()vec1をmoveしないからである。

このように、 iter()は、呼び出し元のVectorをmoveしない。

mapに渡される要素は参照なのか?

fn main() {
    let vec1 = vec![1,2,3,4,5];
    let vec2 = vec1.iter()
                   .map(|i| *i * 3) // OK!
                   .collect::<Vec<i32>>();
}

このコードはコンパイルできる。4行目の map(|i| *i * 3)iは、値ではなく参照だからである。

このように、iter()に連なる mapには、参照が渡される。

結論

VectorIteratorに変換して処理を行いたいとき、

  • そのVectorを後で利用するならiter()を使う。その場合、mapには要素の参照が渡される。
  • そのVectorを後で利用しないならinto_iter()を使う。その場合、mapには要素の値が渡される。

速度について

一応簡単にベンチマークして、iter()into_iter()の間に速度的な差があるのか検証した。 なんとなくiter()の方が遅いような気がするが、誤差幅を考えるとほとんど差がないように見える。

ベンチマークのコード:

#![feature(test)]

extern crate test;

pub fn iter(vec: Vec<i64>) {
    vec.iter().map(|i| i * 2).sum::<i64>();
}

pub fn into_iter(vec: Vec<i64>) {
    vec.into_iter().map(|i| i * 2).sum::<i64>();
}

#[cfg(test)]
mod tests {
    use super::*;
    use test::Bencher;

    #[bench]
    fn bench_iter(b: &mut Bencher) {
        let range = 0..100000;
        let vec = range.collect::<Vec<i64>>();

        b.iter(|| iter(vec.clone()));
    }

    #[bench]
    fn bench_into_iter(b: &mut Bencher) {
        let range = 0..100000;
        let vec = range.collect::<Vec<i64>>();

        b.iter(|| into_iter(vec.clone()));
    }
}

結果:

> cargo bench
   Compiling iterator-bench v0.1.0
    Finished release [optimized] target(s) in 0.61 secs
     Running target/release/deps/iterator_bench-b01db65774dc9996

running 2 tests
test tests::bench_into_iter ... bench:      38,553 ns/iter (+/- 14,812)
test tests::bench_iter      ... bench:      39,507 ns/iter (+/- 20,207)

test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured; 0 filtered out