首页 > 代码库 > Apple的LZF算法解析
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 = 14; private const uint Hsize = (1 << 14); private const uint MaxLit = (1 << 5); private const uint MaxOff = (1 << 13); private const uint MaxRef = ((1 << 8) + (1 << 3));
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, 0, (int)Hsize); uint iidx = 0; uint oidx = 0; var hval = (uint)(((input[iidx]) << 8) | input[iidx + 1]); var lit = 0; for (; ; ) { if (iidx < inputLength - 2) { hval = (hval << 8) | input[iidx + 2]; long hslot = ((hval ^ (hval << 5)) >> (int)(((3 * 8 - Hlog)) - hval * 5) & (Hsize - 1)); var reference = _hashTable[hslot]; _hashTable[hslot] = iidx; long off; if ((off = iidx - reference - 1) < MaxOff && iidx + 4 < inputLength && reference > 0 && input[reference + 0] == input[iidx + 0] && input[reference + 1] == input[iidx + 1] && input[reference + 2] == input[iidx + 2] ) { uint len = 2; var maxlen = (uint)inputLength - iidx - len; maxlen = maxlen > MaxRef ? MaxRef : maxlen; if (oidx + lit + 1 + 3 >= outputLength) return 0; do len++; while (len < maxlen && input[reference + len] == input[iidx + len]); if (lit != 0) { output[oidx++] = (byte)(lit - 1); lit = -lit; do output[oidx++] = input[iidx + lit]; while ((++lit) != 0); } len -= 2; iidx++; if (len < 7) { output[oidx++] = (byte)((off >> 8) + (len << 5)); } else { output[oidx++] = (byte)((off >> 8) + (7 << 5)); output[oidx++] = (byte)(len - 7); } output[oidx++] = (byte)off; iidx += len - 1; hval = (uint)(((input[iidx]) << 8) | input[iidx + 1]); hval = (hval << 8) | input[iidx + 2]; _hashTable[((hval ^ (hval << 5)) >> (int)(((3 * 8 - Hlog)) - hval * 5) & (Hsize - 1))] = iidx; iidx++; hval = (hval << 8) | input[iidx + 2]; _hashTable[((hval ^ (hval << 5)) >> (int)(((3 * 8 - Hlog)) - hval * 5) & (Hsize - 1))] = iidx; iidx++; continue; } } else if (iidx == inputLength) break; lit++; iidx++; if (lit != MaxLit) continue; if (oidx + 1 + MaxLit >= outputLength) return 0; output[oidx++] = (byte)(MaxLit - 1); lit = -lit; do output[oidx++] = input[iidx + lit]; while ((++lit) != 0); } if (lit == 0) return (int)oidx; if (oidx + lit + 1 >= outputLength) return 0; output[oidx++] = (byte)(lit - 1); lit = -lit; do output[oidx++] = input[iidx + lit]; while ((++lit) != 0); return (int)oidx; }
3.
/// <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 = 0; uint oidx = 0; do { uint ctrl = input[iidx++]; if (ctrl < (1 << 5)) { ctrl++; if (oidx + ctrl > outputLength) { return 0; } do output[oidx++] = input[iidx++]; while ((--ctrl) != 0); } else { var len = ctrl >> 5; var reference = (int)(oidx - ((ctrl & 0x1f) << 8) - 1); if (len == 7) len += input[iidx++]; reference -= input[iidx++]; if (oidx + len + 2 > outputLength) { return 0; } if (reference < 0) { return 0; } output[oidx++] = output[reference++]; output[oidx++] = output[reference++]; do output[oidx++] = output[reference++]; while ((--len) != 0); } } while (iidx < inputLength); return (int)oidx; }
以上是LZF算法的代码。
Apple的LZF算法解析
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。