文档章节

Apple的LZF算法解析

彭泽0902
 彭泽0902
发布于 2016/11/24 18:47
字数 740
阅读 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算法的代码。

© 著作权归作者所有

共有 人打赏支持
彭泽0902
粉丝 0
博文 44
码字总数 57771
作品 0
武汉
高级程序员
在多台服务器上简单实现Redis的数据主从复制

Redis的主从复制功能非常强大,一个master可以拥有多个slave,而一个slave又可以拥有多个slave,如此下去,形成了强大的多级服务器集群架构。下面我演示下怎样在多台服务器上进行Redis数据主...

liuhao_sh
2015/08/14
0
0
阿里云开放存储服务的C语言SDK--OSSC

OSSC(Aliyun Open Storage Service C SDK)为阿里云开放存储服务(OSS)提供了一套完整易用的C SDK。 OSSC完全采用C语言开发,并实现了类似面向对象的调用方式,遵循了良好的编码规范,目前O...

大卷卷
2012/10/22
4.2K
0
elasticsearch 的导入导出插件 - elasticsearch -knapsack

Elasticsearch的背包插件。 Knapsack是Elasticsearch的“swiss knife”导出/导入插件。它使用压缩算法(gzip,bzip2,lzf,xz)使用压缩格式(tar,zip,cpio)和Elasticsearch批量格式。 还...

匿名
2017/12/13
65
1
Redis源码解析(1)——源码目录介绍

概念 redis是一个key-value存储系统。和Memcached类似,它支持存储的value类型相对更多,包括string(字符串)、list(链表)、set(集合)和zset(有序集合)。这些数据类型都支持push/pop、add/rem...

nothingfinal
03/07
0
0
Redis源码阅读笔记-快速列表

快速列表 快速列表(quicklist)是由压缩列表(ziplist)组成的一个双向链表,链表中,每一个节点都是以压缩列表(ziplist)的结构保存。 在 Redis3.2 后加入的新数据结构,在列表键中取代了双向链...

Jian_Ming
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

使用xtrabackup完成远程备份

转载收藏,以防丢失 需求 Can I backup remote databases from my local server02-27-2013, 06:17 AMHi, I am using mysqldump so far for taking daily backups of my Production datab......

阿dai
18分钟前
1
0
OSChina 周五乱弹 —— 心情超级好开始乱删库

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @莱布妮子:分享Charli XCX的单曲《Boom Clap》 《Boom Clap》—— Charli XCX 手机党少年们想听歌,请使劲儿戳(这里) 把生命除去上班时间,...

小小编辑
19分钟前
5
7
为什么你的python版本一团糟?因为少了这个操作

坑人的版本 Python 的版本问题一直是个广被吐槽的黑点。以至于有人调侃说: Python 是世界上最好的两种语言! 在这里我要说明下,对于初学者来说,版本间的语法差异其实并不大。现在刚开始学...

crossin
昨天
2
0
Cannot forward after response has been committed

声名:转载自CSDN 通过toncat启动服务器,可以正常登陆访问,登陆进去选择子系统的时候点击登陆的时候,可是去又回到了登陆界面,如此反复就是不能够进入子系统,查看后台报的错误: java.la...

小橙子的曼曼
昨天
2
0
shell编程(告警系统邮件引擎、运行告警系统)

告警系统邮件引擎 1.如果要使用邮件引擎功能,需要调用mail.py文件,放到/usr/local/sbin/mon/mail/目录下即可,具体内容如下: #!/usr/bin/env python#-*- coding: UTF-8 -*-import os,s...

蛋黄_Yolks
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部