FastLZダウンロードFastLZソースコードのダウンロード

FastLZ

C# ソースコード

1.0.0

ダウンロード

概要

FASTLZ（MITライセンス）は、LEMPEL-ZIV 77アルゴリズム（LZ77）のロスレスデータ圧縮のANSI C/C90実装です。一連のテキスト/段落、生のピクセルデータのシーケンス、または多くの繰り返しを伴う他のデータブロックを圧縮するのに適しています。通常、最適な圧縮形式で、画像、ビデオ、およびその他の形式のデータで使用することを意図していません。

FastLzの焦点は非常に高速な圧縮と減圧であり、圧縮率を犠牲にしてそれを行います。例として、Enwik8を圧縮するときのZlibとの比較（詳細についても）：

	比率	圧縮	減圧
Fastlz	54.2％	159 MB/s	305 MB/s
Zlib -1	42.3％	50 MB/s	184 MB/s
Zlib -9	36.5％	11 MB/s	185 mb/s

FASTLZは、多くのゲーム（死のストライクなど）からさまざまなオープンソースプロジェクト（Godot Engine、Facebook HHVM、Apache Traffic Server、Calligra Office、OSV、Nettyなど）まで、多くのソフトウェア製品で使用されています。 Bloscのような他の圧縮プロジェクトの基礎としても機能します。

バイトアリードLZ77のその他の実装については、LZ4、Snappy、密度、LZO、LZF、LZJB、LZRWなどをご覧ください。

使用法

FASTLZは、任意のC/C ++アプリケーションで直接使用できます。他のプログラミング言語/環境には、対応するバインディングを使用します。

錆、木枠で利用可能： cargo install fastlz
Python, available on PyPi: pip install fastlz
javascript、npm： npm install fastlzで利用可能
Ruby、Rubygemsで利用可能： gem install fastlz
github.com/oneoo/lua-fastlz経由でlua

Fastlzは、 fastlz.hとfastlz.c 2つのファイルのみで構成されています。 FASTLZを使用するために、これらのファイルをプロジェクトに追加するだけです。 APIの詳細については、圧縮と減圧を実行するには、 fastlz.h参照してください。

VCPKGユーザーの場合、FASTLZはすでに利用可能です。VCPKG vcpkg install fastlz 。

6packと呼ばれる単純なファイルコンプレッサーは、FastLzの使用方法に関する例として含まれています。対応する分解器は6unpackです。

FASTLZは、GCC、Clang、Visual Studio、さらにはTiny CCなどの人気のあるコンパイラを含む、標準的な強制ANSI C/C90コンパイラをサポートしています。 Fastlzは、Intel/AMD、PowerPC、System Z、ARM、MIPS、およびRISC-Vの多くのアーキテクチャ（32ビットと64ビット、ビッグエンディアンとリトルエンディアン）でうまく機能します。

連続積分システムは、次のシステムでの圧縮抑制ラウンドトリップの広範なセットを実行します。

詳細については、対応するgithubアクションを確認してください。


AMD64	Linux	Windows	macos
GCC
クラン
tinycc
VS 2019
i686	Linux	Windows	macos
GCC
クラン
tinycc
VS 2019
I586	Linux	dos
GCC
	Linux
PowerPc
GCC
PPC64（LE）
GCC
GCC
S390X
GCC
ARMHF
GCC
ARM64
GCC
MIPS（EL）
GCC
GCC
MIPS64（EL）
GCC
GCC
RISCV
GCC
RISCV64
GCC

ブロック形式

Fastlzは、圧縮ブロックと呼ばれるブロックと呼ばれるバイトの配列を、圧縮ブロックと呼ばれる別のバイトの配列に圧縮すると仮定します。圧縮ブロックに何が保存されるかを理解するために、fastLzがブロックを解凍して元の非圧縮ブロックを取得する方法を示すことが実証されています。

ブロックの最初の3ビット、つまり最初のバイトの3つの最も重要なビットはブロックタグです。現在、ブロックタグは、圧縮ブロックを生成するために使用される圧縮レベルを決定します。

ブロックタグ	圧縮レベル
0	レベル1
1	レベル2

ブロックの内容は、圧縮レベルによって異なります。

レベル1のブロック形式

FASTLZレベル1は、8 kBのスライドウィンドウと一致長の最大264バイトのLZ77圧縮アルゴリズムを実装します。

圧縮ブロックは、1つ以上の命令で構成されています。各命令は、1バイトのオペコード、2バイトのオペコード、または3バイトのオペコードから始まります。

命令タイプ	opcode [0]	opcode [1]	opcode [2]
リテラルラン	`000` 、l₄-l₀	-	-
ショートマッチ	m₂-m₀、r₁₂-r₈	r₇-r₀	-
ロングマッチ	`111` 、r₁₂-r₈	m₇-m₀	r₇-r₀

圧縮ブロックでの最初の命令は、常に文字通りの実行であることに注意してください。

文字通りの実行指示

文字通りの実行命令の場合、コードに続く1つ以上のバイトがあります。これはリテラルランと呼ばれます。

opcode[0] 、 Lの5つの最小重要なビットは、オペコードに続くリテラルの数を決定します。 0の値は、1バイトのリテラルランを示し、1は2バイトのリテラルランなどを示します。最小リテラルランは1で、最大のリテラルランは32です。

減圧装置は、オペコードの直後の最初のものから始まるリテラル実行のバイト（ L + 1 ）コピーです。

例：圧縮ブロックが[0x02, 0x41, 0x42, 0x43]の4バイト配列である場合、オペコードは0x02であり、それは3バイトの文字通りの実行を意味します。減圧器は、後続の3バイト[0x41, 0x42, 0x43]を出力バッファーにコピーします。出力バッファーは、（元の）非圧縮ブロック[0x41, 0x42, 0x43]を表します。

ショートマッチ命令

opcode[0] 、 mの3つの最も重要なビットは、一致の長さを決定します。 1の値は3バイトの一致を示し、2は4バイトの一致などを示します。最小一致の長さは3で、最大一致長は8です。

opcode[0]の5ビットの5ビットとopcode[1]の8ビットと組み合わせて、参照オフセットを決定します。オフセットは13ビットでエンコードされるため、最小値は0で、最大は8191です。

次のCコードは、一致の長さと参照オフセットを取得します。

 M = opcode [ 0 ] >> 5 ;
R = 256 * ( opcode [ 0 ] << 5 ) + opcode [ 1 ];

減圧器コピー（M+2）バイトは、出力バッファーのRでオフセットされた場所から始まります。 Rはバックリファレンスであることに注意してください。つまり、0の値は出力バッファーの最後のバイト、1は最後のバイトなどです。

例1 ：圧縮ブロックが[0x03, 0x41, 0x42, 0x43, 0x44, 0x20, 0x02]の7バイト配列である場合、そこには2つの指示があります。最初の命令は、4バイトの文字通りの実行です（ L = 3による）。したがって、減圧器は出力バッファーに4バイトをコピーして[0x41, 0x42, 0x43, 0x44]になります。 2番目の命令は、3バイト（ M = 1 、IE 0x20 >> 5から）の短い一致であり、2のオフセットです。したがって、コンプレッサーは最後の位置から2バイトに戻り、3バイト（ [0x42, 0x43, 0x44] ）をコピーし、出力バッファーに追加します。出力バッファーは、完全な非圧縮データ[0x41, 0x42, 0x43, 0x44, 0x42, 0x43, 0x44]を表します。

例2 ：圧縮ブロック[0x00, 0x61, 0x40, 0x00]の4バイト配列である場合、そこには2つの指示があります。最初の命令は、わずか1バイト（ l = 0 ）の文字通りの実行です。したがって、減圧装置はバイト（ 0x61 ）を出力バッファーにコピーします。出力バッファーは[0x61]になります。 2番目の命令は、4バイト（ M = 2 、IE 0x40 >> 5から）の短い一致と0のオフセットです。したがって、減圧器は0のバック参照を使用して4バイトをコピーします（つまり、 0x61の位置）。出力バッファーは、完全な非圧縮データ[0x61, 0x61, 0x61, 0x61, 0x61]を表します。

長い一致命令

opcode[1] 、 Mの値は、一致の長さを決定します。 0の値は9バイトの一致を示し、1は10バイトの一致などを示します。最小一致長は9で、最大一致長は264です。

5ビットのopcode[0]の5ビットopcode[2]と組み合わせた5ビット、 Rは、参照オフセットを決定します。オフセットは13ビットでエンコードされるため、最小値は0で、最大は8191です。

次のCコードは、一致の長さと参照オフセットを取得します。

 M = opcode [ 1 ];
R = 256 * ( opcode [ 0 ] << 5 ) + opcode [ 2 ];

減圧装置コピー（M+9）バイトは、出力バッファーのRでオフセットされた場所から始まります。 Rはバック参照であり、つまり0の値は出力バッファーの最後のバイトに対応し、1は2番目から最後のバイトなどに対応することに注意してください。

例：圧縮ブロックが[0x01, 0x44, 0x45, 0xE0, 0x01, 0x01]の4バイト配列である場合、そこには2つの指示があります。最初の命令は、長さ2の文字通りの実行です（ L = 1による）。したがって、減圧装置は、2バイトのリテラル実行（ [0x44, 0x45] ）を出力バッファーにコピーします。 2番目の命令は、10の一致長（ m = 1から）と1のオフセットとの長い一致です。したがって、分解器は1のバック参照を使用して10バイトをコピーします（つまり、 0x44の位置）。出力バッファーは、完全な非圧縮データ[0x44, 0x45, 0x44, 0x45, 0x44, 0x45, 0x44, 0x45, 0x44, 0x45, 0x44, 0x45]を表します。

減圧器の参照実装

次の40ラインC関数は、上記のブロック形式のために完全に機能する減圧装置を実装しています。教育を意図していることに注意してください。

 void fastlz_level1_decompress ( const uint8_t * input , int length , uint8_t * output ) {
  int src = 0 ;
  int dest = 0 ;
  while ( src < length ) {
    int type = input [ src ] >> 5 ;
    if ( type == 0 ) {
      /* literal run */
      int run = 1 + input [ src ];
      src = src + 1 ;
      while ( run > 0 ) {
        output [ dest ] = input [ src ];
        src = src + 1 ;
        dest = dest + 1 ;
        run = run - 1 ;
      }
    } else if ( type < 7 ) {
      /* short match */
      int ofs = 256 * ( input [ src ] & 31 ) + input [ src + 1 ];
      int len = 2 + ( input [ src ] >> 5 );
      src = src + 2 ;
      int ref = dest - ofs - 1 ;
      while ( len > 0 ) {
        output [ dest ] = output [ ref ];
        ref = ref + 1 ;
        dest = dest + 1 ;
        len = len - 1 ;
      }
    } else {
      /* long match */
      int ofs = 256 * ( input [ src ] & 31 ) + input [ src + 2 ];
      int len = 9 + input [ src + 1 ];
      src = src + 3 ;
      int ref = dest - ofs - 1 ;
      while ( len > 0 ) {
        output [ dest ] = output [ ref ];
        ref = ref + 1 ;
        dest = dest + 1 ;
        len = len - 1 ;
      }
    }
  }
}