Apple的LZF算法解析

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

有关LZF算法的相关解析文档比较少，但是Apple对LZF的开源，可以让我们对该算法进行一个简单的解析。LZFSE 基于 Lempel-Ziv ，并使用了有限状态熵编码。LZF采用类似lz77和lzss的混合编码。使用3种“起始标记”来代表每段输出的数据串。

接下来看一下开源的LZF算法的实现源码。

1.定义的全局字段：

private readonly long[] _hashTable = new long[Hsize]; private const uint Hlog = ; private const uint Hsize = ( << ); private const uint MaxLit = ( << ); private const uint MaxOff = ( << ); private const uint MaxRef = (( << ) + ( << ));

2.使用LibLZF算法压缩数据：

/// <summary>
/// 使用LibLZF算法压缩数据
/// </summary>
/// <param name="input">需要压缩的数据</param>
/// <param name="inputLength">要压缩的数据的长度</param>
/// <param name="output">引用将包含压缩数据的缓冲区</param>
/// <param name="outputLength">压缩缓冲区的长度（应大于输入缓冲区）</param>
/// <returns>输出缓冲区中压缩归档的大小</returns>
public int Compress(byte[] input, int inputLength, byte[] output, int outputLength)
{
Array.Clear(_hashTable, , (int)Hsize);
uint iidx = ;
uint oidx = ;
var hval = (uint)(((input[iidx]) << ) | input[iidx + ]);
var lit = ;
for (; ; )
{
if (iidx < inputLength - )
{
hval = (hval << ) | input[iidx + ];
long hslot = ((hval ^ (hval << )) >> (int)((( * - Hlog)) - hval * ) & (Hsize - ));
var reference = _hashTable[hslot];
_hashTable[hslot] = iidx;
long off;
if ((off = iidx - reference - ) < MaxOff
&& iidx + < inputLength
&& reference >
&& input[reference + ] == input[iidx + ]
&& input[reference + ] == input[iidx + ]
&& input[reference + ] == input[iidx + ]
)
{
uint len = ;
var maxlen = (uint)inputLength - iidx - len;
maxlen = maxlen > MaxRef ? MaxRef : maxlen;
if (oidx + lit + + >= outputLength)
return ;
do
len++;
while (len < maxlen && input[reference + len] == input[iidx + len]);
if (lit != )
{
output[oidx++] = (byte)(lit - );
lit = -lit;
do
output[oidx++] = input[iidx + lit];
while ((++lit) != );
}
len -= ;
iidx++;
if (len < )
{
output[oidx++] = (byte)((off >> ) + (len << ));
}
else
{
output[oidx++] = (byte)((off >> ) + ( << ));
output[oidx++] = (byte)(len - );
}
output[oidx++] = (byte)off;
iidx += len - ;
hval = (uint)(((input[iidx]) << ) | input[iidx + ]);
hval = (hval << ) | input[iidx + ];
_hashTable[((hval ^ (hval << )) >> (int)((( * - Hlog)) - hval * ) & (Hsize - ))] = iidx;
iidx++;
hval = (hval << ) | input[iidx + ];
_hashTable[((hval ^ (hval << )) >> (int)((( * - Hlog)) - hval * ) & (Hsize - ))] = iidx;
iidx++;
continue;
}
}
else if (iidx == inputLength)
break;
lit++;
iidx++;
if (lit != MaxLit) continue;
if (oidx + + MaxLit >= outputLength)
return ; output[oidx++] = (byte)(MaxLit - );
lit = -lit;
do
output[oidx++] = input[iidx + lit];
while ((++lit) != );
}
if (lit == ) return (int)oidx;
if (oidx + lit + >= outputLength)
return ;
output[oidx++] = (byte)(lit - );
lit = -lit;
do
output[oidx++] = input[iidx + lit];
while ((++lit) != ); return (int)oidx;
}

/// <summary>
/// 使用LibLZF算法解压缩数据
/// </summary>
/// <param name="input">参考数据进行解压缩</param>
/// <param name="inputLength">要解压缩的数据的长度</param>
/// <param name="output">引用包含解压缩数据的缓冲区</param>
/// <param name="outputLength">输出缓冲区中压缩归档的大小</param>
/// <returns>返回解压缩大小</returns>
public int Decompress(byte[] input, int inputLength, byte[] output, int outputLength)
{
uint iidx = ;
uint oidx = ;
do
{
uint ctrl = input[iidx++]; if (ctrl < ( << ))
{
ctrl++; if (oidx + ctrl > outputLength)
{
return ;
} do
output[oidx++] = input[iidx++];
while ((--ctrl) != );
}
else
{
var len = ctrl >> ;
var reference = (int)(oidx - ((ctrl & 0x1f) << ) - );
if (len == )
len += input[iidx++];
reference -= input[iidx++];
if (oidx + len + > outputLength)
{
return ;
}
if (reference < )
{
return ;
}
output[oidx++] = output[reference++];
output[oidx++] = output[reference++];
do
output[oidx++] = output[reference++];
while ((--len) != );
}
}
while (iidx < inputLength); return (int)oidx;
}