Apple的LZF算法解析
Apple的LZF算法解析
彭泽0902 发表于11个月前
Apple的LZF算法解析
  • 发表于 11个月前
  • 阅读 0
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 十分钟定制你的第一个小程序>>>   

    有关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算法的代码。

共有 人打赏支持
粉丝 0
博文 44
码字总数 57771
×
彭泽0902
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: