Range Coder

Range Coderは現在最も良く使われているエントロピー符号化の一つである。最近Range Coderを使う機会があり、ネット上のライブラリを使っていた。しばらく問題なく使えていたのだが、ある時を境にテストコードが通らなくなった。サイズの小さいテストで失敗するようだった。使用したのは以下のサイトにあるソースコード。Range Coderでググると一番上に来るサイトだ。
高速な算術圧縮を実現する「Range Coder」（1/2）：CodeZine http://codezine.jp/article/detail/443
バグの原因を調べたところ、繰り上がりが起こる前に入力が終了した場合に、繰り上がり用に保持されていたバイトを余分に出力してしまうというものだった。これを修正するために、繰り上がりが起こっていない場合は余分なバイトを出力しないようにした。以下がそのパッチである。

diff -Bwbr rc_src/rc.hpp rc_src_patched/rc.hpp
73a74
> 		if (!start) {
74a76
> 		}

境界条件バグなので見つけにくかったのだと思う。何はともあれ、これで安心してライブラリを使うことができるようになった。作業がはかどると良いなぁ・・・。