Deflate (gzip) のアルゴリズムを視覚化してみた
のような感じにエンコードされることが分かります。 自分の好きなデータで試すことができて便利！という話でした。 PS. 以下は実行結果です。 % make % gzip < alice.txt > alice.txt.gz % ./puff -10 alice.txt.gz puff() succeeded uncompressing 1328 bytes 8 compressed bytes unused inpos=406,inbits=224,outpos=0,outbytes=45 41 6c 69 63 65 20 77 61 73 20 62 65 67 69 6e 6e 69 6e 67 20 74 6f 20 67 65 74 20 76 65 72 79 20 74 69 72 65 64 20 6f 66 20 73 69 74 74 A l i c e w a s b
SWFバイナリ編集のススメ番外編 (zlib 伸張) 中編 | GREE Engineering
よやと申します。こんにちわ。 今回は zlib 解説の中編です。前編はこちら ↓ http://labs.gree.jp/blog/2012/01/4082/ SWFバイナリ編集のススメ番外編 (zlib 伸張) 前編 前回、zlib ヘッダのバイナリを解説しました。今回はその後ろに続く Deflateストリームのバイナリ構造についてです。 尚、固定ハフマンまでの説明で長くなり過ぎたので、動的ハフマン(カスタムハフマン)は次回の後編で改めて解説いたします。 前回の復習 zlib は「zlib ヘッダ + Deflate ストリーム + ADLER32」のデータ形式です。尚、通常、zlib ヘッダ無しでも Deflate ストリームだけで圧縮元のデータを復元出来ます。(DICTID が存在すると話が少し厄介ですが、通常見かける事はないでしょう) Deflate はデータを任意の長さのブロック
PNG軽量化の減色と圧縮について | GREE Engineering
このテーブルの番号は 1 Byte になっているため、0-255 の 256 個しか登録できません。そのため、画像で使用されている色が 256 個より多い場合は、なんとかして 256 個にしなくてはいけません。 この「なんとかして 256 色にする」というのが減色処理で、なるべく元の画像からの変化を分からないようにしながら色を減らしていくためのアルゴリズム実装です。（この記事では減色アルゴリズムについての説明は省略します。） テーブルを作成したら、画像のそれぞれのピクセルを RGB 形式からテーブルの何番目の色を使うかに置き換えます。 上図のように、1 ピクセルあたり 24bit 必要だった画像が 1 ピクセルあたり 8bit になったので、データサイズは大体 1/3 になります。 （パレットのデータに最大 3 Byte * 256 = 768 Byte 必要とか、同じように圧縮されないと
Inflate 実装を作って PDF.js の凄さを思い知った話 (前編) : document
4月25 Inflate 実装を作って PDF.js の凄さを思い知った話 (前編) はじめに まずは宣伝から。 このたび JavaScript で Inflate の実装を行いました！ GitHubで公開中で MIT License です。（以前作った Deflate 実装もセットになってます） https://github.com/imaya/zlib.js このエントリーでは、本来ならいかに自分の実装がスゴいかを紹介するところなのですが、前編では自分よりはるか以前に公開された PDF.js の Inflate 実装の素晴らしさを、最適化を進めるにつれて思い知ったのでご紹介させていただくことにします。 バッファ管理の効率の良さ 最初は気持ち悪いと思っていたのですが、一番よく考えてるなと思ったのがバッファ管理です。 PDF.js は Typed Array でバッファを持っているのですが
最近実装した最長一致探索について : document
2月6 最近実装した最長一致探索について はじめに 最近のコミットで最長一致探索部分を書きなおしたらシンプルになったのでメモ替わりに書いておきます。 まず、DEFLATE では chained hash table を使用することが推奨されています。 LZ77 関連では処理の高速化に関していろいろ特許があるようなので、今のところ特許問題のでていないこの方法を使用しています。 chained hash table とは、連続する 3 Byte をハッシュのキーとして辞書を持ち、 ハッシュキーの値に該当位置を記録しておくことで、高速に LZ77 の長さ距離符号の判定を行うことができます。 (なぜ 3 Byte をハッシュキーにするかというと、DEFLATE の長さ距離符号の長さの最小が 3 Byte だからだと思います。) chained hash table を利用したとしても、わかるのは「
LZSS における簡易 lazy matching 実装 : document
2月3 LZSS における簡易 lazy matching 実装 はじめに まず、LZSS とはどういったアルゴリズムなのかを簡単に説明します。 簡単な例をあげます。 "aiueoaiueoaiueo" このような文字列が入力として与えられた時、"aiueo" の繰り返しに注目します。 2回目の "aiueo" は最初の "aiueo" からコピーするようにします。同様に3回目も同じようにします。 すると以下のように表すことができます。 "aiueo[5文字戻り,5文字分参照][10文字戻り,5文字分参照]" (ここでは、これを簡単に "aiueo[5,5][10,5]" と表すことにします。) この表現でもまだ無駄があります。 ここでは5文字分を一区切りとして使用していますが、"aiueoaiueo" 2つの重なりで表現した方が短くなります。 "aiueoaiueo....." "...
SWFバイナリ編集のススメ番外編 (zlib 伸張) 前編 | GREE Engineering
こんにちは。アプリケーション基盤チームのよやと申します。 バイナリの目利きや書き換えを主な業務フィールドとし、1% でも多くのユーザの皆様にサービスをお届けする為、より良質のバイナリを探し求める毎日です。 SWF の番外編として zlib 伸張について２回のブログに分けて解説します。(圧縮処理は対象外です) 前編の今回は概要についてお話し、具体的な実装は後編で扱う予定です。 はじめに SWF フォーマットは zlib 圧縮を多用します。例えば、GIF/PNG 画像は独自画像形式(DefineBitsLossless の BitmapPixelData)に変換後 zlib 圧縮して格納します。 http://labs.gree.jp/blog/2010/12/1902/ SWFバイナリ編集のススメ第五回 (PNG) SWF バイナリの中の zlib 圧縮されたデータが怪しい場合に、zlib
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub - operasoftware/jsunzip: A JavaScript port of Jørgen Ibsens "tiny inflate library" and some additional code for reading a zip archive. All available under the zlib/libpng license.
Build software better, together