・lze とは

「LZSS亜種圧縮/展開アルゴリズムにより作られたデータ圧縮/展開ツールとデコーダ」です。作者は GORRY氏です。
詳細は以下をご参照ください。
http://gorry.haun.org/pw/?lze

・C#版 lzeエンコーダ/デコーダ(ダウンロード)

オリジナルはC言語によるエンコード/デコードルーチンが提示されておりましたが、Windows環境であればC#コンパイラが(暗黙的に)インストールされていることを踏まえ、これを C# にベタ移植しました。

[2020/07/29]指摘いただいた[ファイルサイズが小さいとき正しく圧縮できない][テキストテーブルが溢れて例外を発生する]2つのbugを修正しています。

C#版lze[ダウンロード]

コンパイル方法

コマンドプロンプトより、

%windir%\Microsoft.NET\Framework\v4.0.30319\csc.exe lze.cs

でコンパイルすれば lze.exe が生成されます。

使用方法

lze e infile outfile (Encode;圧縮)
lze d infile outfile (Decode;展開)

のようにして使用します。

・lze 展開コードとは

lze圧縮されたデータを展開(デコード)するプログラムです。各CPU/MPUのアセンブリ言語にて記述されています。
lzeはオリジナルとして8086(x86-16)と68000のアセンブラによる展開ルーチンが公開されておりますが8bit CPU/MPU用はありませんでした。作者であるGORRY氏より「Z80用も簡単に実装できますよ」と話を振られたためまずはZ80版(初期版)を実装してみました。本ページにアップロードされているのはその改良版となります(初期版はアップロードされていません)。
また、その他のCPU/MPU用は勢いで実装しました。

・lze 展開コードについて(ダウンロード)

次の各CPU用を用意しました。CPU名をクリックするとソースコードがダウンロードできます。
SRCにlzeソース+4(*1)、DSTに展開先アドレスを入れて DECODE_LZE をサブルーチン・コールすれば展開されます。

CPU	SRC	DST	備考
Z80	HL	DE	初期リリースでは使用しなかったIYをこのバージョンでは使用しています(Upgrade時には注意)。
Z80	HL	DE	Z80版のバリエーションです。圧縮率が低めのデータで高速動作します
8080	HL	DE
6800	X	A(H),B(L)
6502	LZEptr(zpg)	DECODEPtr(zpg)(*2)
6809	X	U
SC61860	(*3)	(*3)
LR35902	HL	DE

(*1)【"+4"は忘れないようにしてください】。lzeファイルは先頭4バイトにBig Endianで"展開後のサイズ情報"が付与されています。この情報は展開時に必要ない情報ですので、+4したものをSRCに入れて呼び出してください

(*2)ソースコード参照。Zero Page上のメモリに格納してJSRしてください

(*3)次のようにして呼び出します

LIDP SDDW CALL DECODE_LZE ... SDDW: DW LZE_DATA+4-1 ;SRC DW DST-1 ;DST

IXL,IYS命令を使用しているので、予め-1したアドレスを外部メモリ上に用意してCALLしてください。SRCは+4-1=+3となります

・雑感

母数1に対してデータを取ったところ(つまり全く網羅的にはやってません)、ビットパターン1(後述)のデータが多かったため、それをより高速に処理するバリエーションをZ80に実装してみました。
Z80以外のCPU/MPU用はあまり慣れていないため、改良の余地はあると思います。

・lzeアルゴリズムの概略

lzeデータはビットストリームによるフラグと未圧縮のデータまたは距離情報から構成されています。ビットストリームのパターンにより大きく3分岐しており

ビットパターン	アクション
1	1バイトの未圧縮のデータを書き込む
00	コピー:次のビットパターン2bitが長さ、1バイトの距離情報
01	コピー:2バイトの"距離+長さ"情報;長さが0の時はさらに1バイトの長さ情報

となります。

01の2バイトはBig Endianです。16bit データの"上位13bit が距離"、"下位3bitが長さ"を示します。

距離情報とは、カレントの展開位置ポインタから減じる(=常に負の)値です。

つまり"コピー"は、カレント書き込み先ポインタから"距離"を相対的に減じた位置から"長さ"バイトぶんコピーするという動作になります。

・8bit専用改修案

ビットパターン01のとき2バイト(16bit)情報から、「上位13bitの距離情報」と「下位3bitの長さ情報」を取り出す必要があります。16bit以上のCPUであれば16bitの3bit右シフトは簡単に実行出来るので全く問題はありません(オリジナルにはx86-16/MC68000用のコードがあることから、16bit CPU/MPUを前提にしていたのかもしれません)。
ところが8bit CPU/MPUには16bitの3回の右シフトを容易に行える命令はありません。8bitずつ上位に分けて行う必要があり、この処理が冗長になってしまいます(各CPU/MPUに移植していずれもこの処理に命令を多く費やしていると感じてます)。
もし、これを「上位3bitを長さ」「下位13bitを距離」に入れ替えれば、8bit CPU/MPUでも処理しやすくなります。"長さ"を取り出すには上位8bitを3回左ローテートするだけで良くなるからです。
オリジナルを重視したので上記改修案は全く反映しておりませんが、興味がある方は改修してみてはいかがでしょうか。なお、この改修については当然ながらエンコード(圧縮)側も対処する必要があります。

・著作権等

これらのルーチンは一切の制限なく使用・改造・配布等を行うことができます。

一つ上へ

トップへ