エンジニアのスキルを試すコードパズル ─この問題,あなたは解けますか?

第5回 小飼弾からの挑戦(第1回)解説編

この記事を読むのに必要な時間:およそ 2 分

今回は,この連載の第1回百聞は一見に如かず~文字列処理+画像処理=? ─小飼弾からの挑戦」⁠ の解説編です。

解答数と言語別の内訳は

小飼弾です。答案作成,おつかれさまでした。

総解答数は23(同一応募者による重複含む)⁠うち正解は(やや甘い採点で)7でした。ちょっと難しかったかな? 言語別の内訳は次のとおり。

表1 言語別解答数

言語解答数正答数
Perl51
Python51
Java21
PHP10
Ruby10
C10
C++11
R11
Shell Script11
Squeak Smalltalk11
【番外】
日本語20
URL10

「番外」となっているのは,日本語もURLも実行不能なので。ただしURLの方は,私の以下のブログエントリを指し示していたので,正解にたどり着いたといえばたどり着いたことにはなります。

しかしコーダーであれば,自分のコードで示すべき。謹んで失格とさせていただきました。

解答評価のポイント

アルゴリズム(およびJavaScriptによる実装)は,同エントリにあるとおりです。

Perlによる実装も本記事の末尾に載せておきます。具体的には,24bitフルカラー映像を16bitに間引いて,空いた8bitにメッセージを埋め込めばよいわけです。具体的には以下となります。

   Message:mmmmmmmm
   Pixel:  RRRRRmmmGGGGGGmmBBBBBmmm

なぜPNGやBMPはOKでJPEGはだめなのか,という理由もここにあります。ロスレスなフォーマットでないと,正確にピクセルを再現できないからです。

せっかく画像をアップロードしても,JPEGに変換されてしまう場合はよってNG。はてなフォトライフはこういう場合に不適です。

また,1ピクセルに1byteのメッセージを埋め込む以上,ピクセル数に過不足がある場合の処理も問題になります。不足だとエラー,過剰な場合はNULLターミネイト('\0'をメッセージ末尾に足す)というのが正解です。

しかし,これを忘れていた解答が1件ありました。⁠やや甘い採点で」とあるのは,これを「合格」に含めたためです。

きちんとテストを!

きちんとテストをした上で答案を提出しなかった人が多かったのは残念な点です。今回,こんなコメントを載せていた方がいらっしゃいました。

   # 4ピクセルを使って1バイトを埋め込む。
   # 赤成分に4bit,青成分に4bitを割り振る。
   # 人間の目は緑に敏感だとかというのをどこかで聞いたので,
   # 緑成分は変更しないでみる。気休め程度かも。

しかし,テストは以下のようにかんたんです。

デコーダー
⇒問題のembedded.pngからメッセージがきちんと取り出せればよい
エンコーダー
⇒source.pngにメッセージを埋め込んで,結果の映像がembedded.pngとピクセル単位で合致すればよい

にもかかわらず,このコメントは明らかにそれを怠っていることを示しています。

濫用可能なコードを書いたら幇助罪に?

ところで,この記事を書いている最中に,ひろゆきこと西村博之氏が麻薬特例法違反ほう助容疑で書類送検されたというニュースが入ってきました。2ちゃんねるで薬物取引のやりとりが行われていたにもかかわらず,それを放置したからとのことです。

しかし,これは牽強付会にもほどがあるというものでしょう。同じことは,2ちゃんねるでなくとも,ユーザによるコンテンツをアップロードできるサイトであればどこでも可能です。そして本記事の問題が示すとおり,無害なデータを装うことはあまりにかんたんなのですから。

私や解答者のみなさんも,このようなステガノグラフィーが用いられたら書類送検の対象となってしまうのでしょうか。Winny著作権法幇助事件は無罪が確定したものの,最高裁判決が出るまではとてもコード書くどころではなかった,と金子氏ご本人から伺っております。

濫用可能なコードを書いたら幇助罪が適用されるとなっては,だれがコードを公開するというのでしょう。一オープンソースプログラマーとして心配でなりません。

  • Dan the Open Source Programmer

リスト Perlによる実装例

#!/usr/bin/env perl
use strict;
use warnings;
use Imager;
use Perl6::Slurp;

sub transcode {
   my ( $imgfile, $txtfile, $outfile ) = @_;
   my $img = Imager->new();
   $img->read( file => $imgfile ) or die $img->errstr;
   $img->write( data => \my $pnm, type => 'pnm' ) or die $img->errstr;
   my $hdr = do {
       $pnm =~ s/((?:[^\n]+\n){4})//;
       $1;
   };
   my @pnm = map { ord } split //, $pnm;
   if ( !$txtfile ) {    # decode
       my $txt = '';
       for my $i ( 0 .. +@pnm / 3 ) {
           my $ord =
             ( ( $pnm[ 3 * $i     ] & 0b00000111 ) << 5 ) +
             ( ( $pnm[ 3 * $i + 1 ] & 0b00000011 ) << 3 ) +
             (   $pnm[ 3 * $i + 2 ] & 0b00000111 );
           last if !$ord;
           $txt .= chr $ord;
       }
       print $txt;
   }
   else {                # encode
       my $txt = slurp $txtfile;
       die "image too small" if @pnm < length $txt;
       my $i = 0;
       for my $ord ( unpack 'C*', $txt . "\0" ) {
           my $r = ( $ord & 0b11100000 ) >> 5;
           my $g = ( $ord & 0b00011000 ) >> 3;
           my $b = $ord & 0b00000111;
           $pnm[ $i     ] = ( $pnm[ $i     ] & 0b11111000 ) | $r;
           $pnm[ $i + 1 ] = ( $pnm[ $i + 1 ] & 0b11111100 ) | $g;
           $pnm[ $i + 2 ] = ( $pnm[ $i + 2 ] & 0b11111000 ) | $b;
           $i += 3;
       }
       $pnm = $hdr . pack 'C*', @pnm;
       $img->read( data => $pnm ) or die $img->errstr;
       if ($outfile) {
           $img->write( file => $outfile ) or die $img->errstr;
       }
       else {
           $img->write( fh => \*STDOUT, type => 'png' ) or die $img->errstr;
       }
   }
}

transcode @ARGV;
__END__

著者プロフィール

小飼弾(こがいだん)

ブロガー/オープンソースプログラマー/投資家などなど。ディーエイエヌ(有)代表取締役。1999~2001年(株)オン・ザ・エッヂ(後のライブドア)取締役最高技術責任者(CTO)。プログラミング言語Perlでは,標準添付最大のモジュールEncodeのメンテナンス担当。著書に『アルファギークに逢ってきた』(2008年5月,技術評論社)。

ブログは『404 Blog Not Found』
URL:http://blog.livedoor.jp/dankogai/

コメント

  • Re:

    不正解とするには悪魔の証明が必要かと思ってたけど違うのか。

    Commented : #1  おつかれ (2013/01/12, 07:34)

コメントの記入