235 lines
6.8 KiB
C#
235 lines
6.8 KiB
C#
namespace AssetExtractor;
|
||
|
||
/// <summary>
|
||
/// Decoder for the LZHUF format (LZSS + adaptive Huffman, Okumura/Yoshizaki 1988),
|
||
/// as written by the Delphi TLZRW1 component in "Good" mode.
|
||
/// Stream layout: [4B magic "LZH!" = 0x4C5A4821 LE][4B LE original size][LZHUF bitstream].
|
||
/// </summary>
|
||
public static class Lzh
|
||
{
|
||
public const uint LzhMagic = (((((uint)'L' << 8) + 'Z') << 8) + 'H' << 8) + '!';
|
||
|
||
const int N = 4096; // ring buffer size
|
||
const int F = 60; // lookahead buffer size
|
||
const int Threshold = 2;
|
||
const int NChar = 256 - Threshold + F; // 314 character codes
|
||
const int T = NChar * 2 - 1; // 627, size of freq table
|
||
const int R = T - 1; // 626, root position
|
||
const int MaxFreq = 0x8000;
|
||
|
||
// Tables for decoding the upper 6 bits of the match position
|
||
static readonly byte[] DCode = BuildDCode();
|
||
static readonly byte[] DLen = BuildDLen();
|
||
|
||
static byte[] BuildDCode()
|
||
{
|
||
// Canonical LZHUF d_code table: value 0 ×32; 1..3 ×16; 4..11 ×8; 12..23 ×4; 24..47 ×2; 48..63 ×1
|
||
var t = new byte[256];
|
||
int i = 0, v = 0;
|
||
foreach (var (values, run) in new[] { (1, 32), (3, 16), (8, 8), (12, 4), (24, 2), (16, 1) })
|
||
for (int g = 0; g < values; g++, v++)
|
||
for (int k = 0; k < run; k++)
|
||
t[i++] = (byte)v;
|
||
return t;
|
||
}
|
||
|
||
static byte[] BuildDLen()
|
||
{
|
||
// Canonical LZHUF d_len table: 3 ×32, 4 ×48, 5 ×64, 6 ×48, 7 ×48, 8 ×16
|
||
var t = new byte[256];
|
||
int i = 0;
|
||
foreach (var (count, val) in new[] { (32, 3), (48, 4), (64, 5), (48, 6), (48, 7), (16, 8) })
|
||
for (int k = 0; k < count; k++)
|
||
t[i++] = (byte)val;
|
||
return t;
|
||
}
|
||
|
||
public static byte[] Decompress(byte[] file)
|
||
{
|
||
if (file.Length < 8 || BitConverter.ToUInt32(file, 0) != LzhMagic)
|
||
throw new InvalidDataException("Not an LZH!-compressed TLZRW1 stream.");
|
||
int origSize = BitConverter.ToInt32(file, 4);
|
||
return Decode(file, 8, origSize);
|
||
}
|
||
|
||
static byte[] Decode(byte[] src, int srcOffset, int origSize)
|
||
{
|
||
var output = new byte[origSize];
|
||
int outPos = 0;
|
||
|
||
// adaptive Huffman state
|
||
var freq = new int[T + 1];
|
||
var prnt = new int[T + NChar];
|
||
var son = new int[T];
|
||
|
||
// init tree
|
||
for (int i = 0; i < NChar; i++)
|
||
{
|
||
freq[i] = 1;
|
||
son[i] = i + T;
|
||
prnt[i + T] = i;
|
||
}
|
||
for (int i = 0, j = NChar; j <= R; i += 2, j++)
|
||
{
|
||
freq[j] = freq[i] + freq[i + 1];
|
||
son[j] = i;
|
||
prnt[i] = j;
|
||
prnt[i + 1] = j;
|
||
}
|
||
freq[T] = 0xFFFF;
|
||
prnt[R] = 0;
|
||
|
||
// ring buffer, initialized to spaces
|
||
var ring = new byte[N + F - 1];
|
||
Array.Fill(ring, (byte)0x20);
|
||
int r = N - F;
|
||
|
||
// bit reader
|
||
int srcPos = srcOffset;
|
||
uint getbuf = 0;
|
||
int getlen = 0;
|
||
|
||
int GetBit()
|
||
{
|
||
while (getlen <= 8)
|
||
{
|
||
uint b = srcPos < src.Length ? src[srcPos++] : 0u;
|
||
getbuf |= b << (8 - getlen);
|
||
getlen += 8;
|
||
}
|
||
int result = (int)((getbuf >> 15) & 1);
|
||
getbuf = (getbuf << 1) & 0xFFFF;
|
||
getlen--;
|
||
return result;
|
||
}
|
||
|
||
int GetByte()
|
||
{
|
||
while (getlen <= 8)
|
||
{
|
||
uint b = srcPos < src.Length ? src[srcPos++] : 0u;
|
||
getbuf |= b << (8 - getlen);
|
||
getlen += 8;
|
||
}
|
||
int result = (int)((getbuf >> 8) & 0xFF);
|
||
getbuf = (getbuf << 8) & 0xFFFF;
|
||
getlen -= 8;
|
||
return result;
|
||
}
|
||
|
||
void Update(int c)
|
||
{
|
||
if (freq[R] == MaxFreq)
|
||
Reconstruct();
|
||
|
||
c = prnt[c + T];
|
||
do
|
||
{
|
||
int k = ++freq[c];
|
||
// if order is disturbed, swap nodes
|
||
int l = c + 1;
|
||
if (k > freq[l])
|
||
{
|
||
while (k > freq[l + 1]) l++;
|
||
freq[c] = freq[l];
|
||
freq[l] = k;
|
||
|
||
int i = son[c];
|
||
prnt[i] = l;
|
||
if (i < T) prnt[i + 1] = l;
|
||
|
||
int j = son[l];
|
||
son[l] = i;
|
||
|
||
prnt[j] = c;
|
||
if (j < T) prnt[j + 1] = c;
|
||
son[c] = j;
|
||
|
||
c = l;
|
||
}
|
||
c = prnt[c];
|
||
} while (c != 0);
|
||
}
|
||
|
||
void Reconstruct()
|
||
{
|
||
// collect leaf nodes, halve frequencies
|
||
int j = 0;
|
||
for (int i = 0; i < T; i++)
|
||
{
|
||
if (son[i] >= T)
|
||
{
|
||
freq[j] = (freq[i] + 1) / 2;
|
||
son[j] = son[i];
|
||
j++;
|
||
}
|
||
}
|
||
// rebuild internal nodes
|
||
for (int i = 0, k = NChar; k < T; i += 2, k++)
|
||
{
|
||
int f = freq[i] + freq[i + 1];
|
||
int l = k;
|
||
while (f < freq[l - 1]) l--;
|
||
Array.Copy(freq, l, freq, l + 1, k - l);
|
||
freq[l] = f;
|
||
Array.Copy(son, l, son, l + 1, k - l);
|
||
son[l] = i;
|
||
}
|
||
// reconnect parent pointers
|
||
for (int i = 0; i < T; i++)
|
||
{
|
||
int k = son[i];
|
||
prnt[k] = i;
|
||
if (k < T) prnt[k + 1] = i;
|
||
}
|
||
}
|
||
|
||
int DecodeChar()
|
||
{
|
||
int c = son[R];
|
||
while (c < T)
|
||
c = son[c + GetBit()];
|
||
c -= T;
|
||
Update(c);
|
||
return c;
|
||
}
|
||
|
||
int DecodePosition()
|
||
{
|
||
// upper 6 bits from table
|
||
int i = GetByte();
|
||
int c = DCode[i] << 6;
|
||
int j = DLen[i] - 2;
|
||
// read lower 6 bits verbatim
|
||
while (j-- > 0)
|
||
i = (i << 1) + GetBit();
|
||
return c | (i & 0x3F);
|
||
}
|
||
|
||
while (outPos < origSize)
|
||
{
|
||
int c = DecodeChar();
|
||
if (c < 256)
|
||
{
|
||
output[outPos++] = (byte)c;
|
||
ring[r] = (byte)c;
|
||
r = (r + 1) & (N - 1);
|
||
}
|
||
else
|
||
{
|
||
int pos = (r - DecodePosition() - 1) & (N - 1);
|
||
int len = c - 255 + Threshold;
|
||
for (int k = 0; k < len && outPos < origSize; k++)
|
||
{
|
||
byte b = ring[(pos + k) & (N - 1)];
|
||
output[outPos++] = b;
|
||
ring[r] = b;
|
||
r = (r + 1) & (N - 1);
|
||
}
|
||
}
|
||
}
|
||
|
||
return output;
|
||
}
|
||
}
|