sliding_window_compressを作りました。 特許に引っかかるとマズいので、一致文字列の検索はとりえず単純な検索(通称:バカサーチ)で実装しています。 sliding_window.hppの差分 また、スライド辞書のテスト用にLZSSのラッパーを用意しました。 <hamigaki/iostreams/filter/lzss.hpp> テストコード</hamigaki/iostreams/filter/lzss.hpp>…

lh6/7対応といいつつ全然テストしてなかったので、試してみたら案の定動きませんでした。 lh6/7だとスライド辞書のサイズが大きくなっている分、一致位置のビット長のハフマンテーブルが大きくなっているようです。 lzhuff.hppの差分 手元の適当な書庫で試し…

どうもプロファイリングのやり方がマズかったようです。 VC++でもg++でも似た傾向になるだろうと考えていたのですが、Cygwin/MinGWのSjLj例外処理が非常に遅く、プログラム全体のパフォーマンスを低下させていました。 特にCygwinの場合は異常に遅いです。お…

既にLHAとはほとんど関係なくなってますが、プロファイルをとるときに-O2を指定していなかったので、もう一度。 % cumulative self self total time seconds seconds calls s/call s/call name 46.93 12.54 12.54 _Unwind_SjLj_Register 22.75 18.62 6.08 _U…

真面目にハフマンツリーを作成するようにしました。 huffman.hppの差分 ツリーの作成に時間がかかりそうで避けていたのですが、参照回数の方が圧倒的に多いため、かなり速くなりました。 この状態でgprofの結果はこうです。 Each sample counts as 0.01 seco…

ようやくLZHデコード処理を組み込みました。 対応ヘッダはLevel 0〜2で、圧縮方法はlh4〜lh7をサポートしています。 <hamigaki/iostreams/filter/sliding_window.hpp> <hamigaki/iostreams/filter/lzhuff.hpp> lzh_file.hppの差分 性能を測るため、23MBの適当なLZHファイルの展開速度を計測してみました。 ツール 時間 UNLHA32.DLL 5秒 lzh_file_so</hamigaki/iostreams/filter/lzhuff.hpp></hamigaki/iostreams/filter/sliding_window.hpp>…

既にご存知の方も多いと思いますが、gzipに複数の脆弱性が見つかっています。 http://oku.edu.mie-u.ac.jp/~okumura/blog/node/1047 修正パッチを確認したところ、自分のハフマンデコード処理にも同様の問題があったので修正しました。 huffman.hppの差分 テ…

とりあえす、LZHのLevel 0/1ヘッダーをサポートしました。 <hamigaki/iostreams/device/lzh_file.hpp> 仕様の確認などにも手間取って、LZHUFの組み込みまではできていません。 Level1ヘッダの実装中にboost::restriction::seek()の戻り値が変なことに気が付きました。 最初はバグかと思ったのですが、</hamigaki/iostreams/device/lzh_file.hpp>…

今日はLHAの方はお休みして、１週間近く放置していたLinux版Hamigaki.Coroutineのyield_to()でクラッシュする問題を調査しました。 浮動小数点例外が発生していたので、コンテキストの切り替えで浮動小数点レジスタが保存されていないのかなとも思ったのです…

一応、LZSSの展開までできましたが、インタフェースをどうするかで迷っています。 今のところ、インタフェースはこうなっています。 template<class Input> class sliding_window_decompressor { public: typedef char char_type; struct category : public boost::iostre</class>…

ハフマンデコーダができました。 <hamigaki/iostreams/utility/huffman.hpp> huffman_decoderはこんな感じのクラスです。 template< class Value, // 符号化前の値の型 std::size_t Bits // 符号長 > class huffman_decoder { public: typedef typename boost::uint_t<Bits>::least code_type; typedef Valu</bits></hamigaki/iostreams/utility/huffman.hpp>…

ハフマンデコードの処理が大体できて、ビット単位ストリームに必要な機能も見えてきました。 ビット単位の操作とはいえ、メモリやディスクの上ではバイトやワードの単位でしか存在できません。そのため、ビットストリームの終端にはビットの端数がでることが…

LHAがLZSSとハフマン符号化を使っていることは有名ですが、自分は今までこの２つをどう繋ぐのか知りませんでした。 ようやく理解できたのでまとめておきます。 LZSSの出力は、 (0、不一致記号) (1、一致位置、一致長) のいずれかですが、LHAのLZHUFアルゴリ…

LHA用にビット単位の読み書きクラスを書いています。 ビット単位の書き込みといえばBoost.CRCにあったなと思い、インタフェースを確認したところ、こうなっていました。 template < std::size_t Bits > class crc_basic { public: void process_bit( bool bi…

CRCのチェックと無圧縮(lh0形式)のファイルの読み出しを実装しました。 <hamigaki/iostreams/device/lzh_file.hpp> lzh_file_source自体は書庫中のエントリを辿って、解凍(LHA用語)後のデータを読み出す機能しかありません。 各エントリをファイルシステム上にどう展開するかはライブラリユーザー次第</hamigaki/iostreams/device/lzh_file.hpp>…

構造体を入れ子にした場合に対応しました。 binary_io.hppの差分 struct_traits.hppの差分 struct inner { boost::uint32_t a; char b; }; struct outer { inner a; char b; }; namespace hamigaki { template<> struct struct_traits<inner> { typedef boost::mpl:</inner>…

MPLの力技で構造体のバイナリ読み書きをやってみました。 <hamigaki/binary_io.hpp> <hamigaki/struct_traits.hpp> 使い方はこんな感じです。 #include <hamigaki/binary_io.hpp> #include <boost/mpl/list.hpp> #include <boost/cstdint.hpp> #include <iostream> #include <fstream> #include <cassert> #include <cstring> // LZH Level2ヘッダ // 構造体にパディングが入っても…</cstring></cassert></fstream></iostream></boost/cstdint.hpp></boost/mpl/list.hpp></hamigaki/binary_io.hpp></hamigaki/struct_traits.hpp></hamigaki/binary_io.hpp>

新たなネタ(実際にはライブラリのネタのネタ)としてBoost.IostreamsでLHA書庫ファイルの読み書きをやってみます。 ZIPは誰かやってそうなのでLHAです。 ヘッダの仕様は、 http://homepage1.nifty.com/dangan/Content/Home.html あたりを参考にしています。 …

Boost.Iostreamsでは、今のところBlockingデバイスとNon-Blockingデバイスを区別する方法がありません。 そのため、ブロック操作が必要な場合は、 io::non_blocking_adapter<Sink> nb(snk); io::write(nb, buf, size);のようにnon_blocking_adapterでラップして強</sink>…

Boost.Coroutineのドキュメントの「Further Development」の項にgeneratorのOutput Iteratorなるものが書かれているのを見つけたので、一足先に実装してみました。 <hamigaki/coroutine/processor.hpp> いつも通りテストコードの抜粋を貼っておきます。 typedef coro::processor<int> processor_type</int></hamigaki/coroutine/processor.hpp>…

coroutine::selfにyield_to()を実装しました。 まずはyield_to()の概要から説明しましょう。 typedef coro::coroutine<void()> coroutine1_type; typedef coro::coroutine<void()> coroutine2_type; void coroutine1_body(coroutine1_type::self& self); void coroutine2_bod</void()></void()>…

昨日の1件を追っていったところ、どうも下記の問題に集約されるようです。 class hoge { public: // (09/10: コロン忘れを訂正) hoge(){} template<class T> hoge(T x, int dummy=0) { } }; int main() { hoge h1; hoge h2(h1, 0); }結果は、 コンパイラ 結果 Visual </class>…

shared_coroutineもサポートしました。 加えてcoroutineにはmove semanticsっぽいコピー操作(単にauto_ptrに入れただけ)を追加です。 <hamigaki/coroutine/detail/coroutine_template.hpp> coroutineとshared_coroutineの違いはauto_ptrとshared_ptrの違いみたいなものです。 現状のBoost.Coroutineの実装ではin</hamigaki/coroutine/detail/coroutine_template.hpp>…

coroutineのコードを整理しつつ、POSIXのucontextを使った実装も追加しました。 <hamigaki/coroutine/detail/posix_user_context.hpp> スタック用のメモリはHamigaki.Detailのvirtual_memoryを使っています。 Hamigaki.Detailはヘッダファイルからインクルードしないはずでしたが、早くも破綻です。 ucontextはf</hamigaki/coroutine/detail/posix_user_context.hpp>…

Boost.Preprocessorで3引数以上にも対応しました。 かなり読みにくくなっています。 <hamigaki/coroutine/detail/coroutine_template.hpp> 内部で boost::functionN < R,self&,T1,T2,...,Tn > を使っているため、コルーチンの引数は(BOOST_FUNCTION_MAX_ARGS-1)個までに制限されます。(つまり既定では9個まで) </hamigaki/coroutine/detail/coroutine_template.hpp>…

pthread_contextに引き続き、fiber_contextも作成しました。 <hamigaki/coroutine/detail/fiber_context.hpp> これに合わせて、coroutineも変更です。 <hamigaki/coroutine/detail/coroutine0.hpp> ここまでは、クラス構成を変更しただけです。 次に1引数の場合、 <hamigaki/coroutine/detail/coroutine1.hpp> operator()の引数とyield()の戻り値が加わります。 2引数になると、 </hamigaki/coroutine/detail/coroutine1.hpp></hamigaki/coroutine/detail/coroutine0.hpp></hamigaki/coroutine/detail/fiber_context.hpp>

現時点のHamigaki.Coroutineのcoroutineは引数なし戻り値ありのコルーチンのみ対応しています。 coroutineのレベルで複数の実装を吸収しているため、これを汎用化させると実装ごとに汎用化の作業が発生してしまい、よくありません。 coroutineより下のレベル…

http://d.hatena.ne.jp/y-hamigaki/20060407 から悩み続けてきたEnumerate系関数のiterator化もHamigaki.Coroutineのおかげでようやく解決しました。 今やDirectSoundデバイスとDirectSoundCaptureデバイスはIteratorで列挙可能です。 direct_sound.hppの差…

やっぱりスタックをコピーするだけでは駄目なようなので、諦めてスレッドを使った実装を追加しました。 <hamigaki/coroutine/detail/thread_coroutine.hpp> 実装にBoost.Threadを使ったので、別途ライブラリのリンクが必要です。 コルーチンが別スレッドで動作するため、呼び出し元とスレッド固有領域が別にな</hamigaki/coroutine/detail/thread_coroutine.hpp>…

以下はBBv1に関する覚え書き。 bjam --verbose-test テストに失敗しなくても実行結果を表示する。 bjam --debugger=gdb テストの実行時にgdbを起動する。 bjam --debugger=vsjitdebugger テストの実行時にVisual Studioを起動する。