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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏斑斓

MongoDB的数据建模

MongoDB是一种面向Document的NoSQL数据库,如果我们还是按照RDB的方式来思考MongoDB的数据建模,则不能有效地利用MongoDB的优势;然...

3106
来自专栏机器之心

资源 | 神经网络框架Chainer发布2.0正式版:CuPy独立

选自GitHub 机器之心编译 参与:李泽南、吴攀 Chainer 是一个灵活的神经网络框架,它的一个主要目标就是展现灵活性,允许我们用简单直观的方式编写出复...

39913
来自专栏落影的专栏

H.264学习笔记

H.264组成 1、网络提取层 (Network Abstraction Layer,NAL) 2、视讯编码层 (Video Coding Layer,VCL)...

3115
来自专栏Fish

CUDA C最佳实践-CUDA Best Practices(三)

10. 运行配置优化 10.1. 占用 10.1.1. 计算占用 10.2. 同步Kernel执行 10.3. 多上下文 10.4. 隐藏寄存器依赖 10.5....

19510
来自专栏不会写文章的程序员不是好厨师

伪共享(False Sharing)和缓存行(Cache Line) 大杂烩

在上篇介绍LongAdder的文章中,我们最后留下了一个问题,为什么Cell中要插入很多个实际上并没有使用的Long变量?这个问题就得从False Sharin...

891
来自专栏Star先生的专栏

Tensorflow 术语表

本文主要简要介绍了广播操作、Graph(图)、Session(会话)、Tensor 等13个 Tensorflow 术语表。希望对大家了解学习 Tensorfl...

8311
来自专栏人工智能LeadAI

TensorFlow的Debugger调试实例

之前有翻译整理过关于TensofFlow的Debugger的简单教程,具体内容见这里。这次用自己实际的例子,来简要的做个使用介绍。 首先是代码遇到了问题,训练过...

3336
来自专栏吉浦迅科技

DAY17:阅读纹理内存之纹理引用API

1212
来自专栏漫漫深度学习路

tensorflow自定义op:work_shard

强行解释 work_shard 在学习 tensorflow 自定义 op 的时候碰到的,google 了一下,也没有找到详细的介绍,难道是姿势不对?? ...

2747
来自专栏Aloys的开发之路

OOAD与UML笔记

UML基础介绍 1.UML的定义 统一建模语言(UML)是一种图形化的语言,它可以帮助我们在OOAD过程中标识元素、构建模块、分析过程并可通过文档说明系统中的重...

1808

扫码关注云+社区