文档章节

Apple的LZF算法解析

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

© 著作权归作者所有

共有 人打赏支持
彭泽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
12306为什么不申请信任的CA证书

访问12306网站如果使用https,可能会出现如下证书问题 即使安装了官网上的证书也会提示如下问题(Chrome+IE) 因为这个证书只用于kwfy.12306.cn网站,而不是www.12306.cn。 并且12306的网站必...

iman123
2014/12/26
4.9K
12
dbexpress 连接 mysql

program Project1; {$APPTYPE CONSOLE} {$R *.res} uses System.SysUtils,data.DB, data.DBXCommon,classes, data.sqlexpr,vcl.dialogs, Data.DBXMySQL; var fsqlconn:Tsqlconnection; begin......

vga
2014/05/30
0
0
Apple Pay 应用内支付流程分析

接入方式 Apple Pay接入方式的选择上有两种。一种是使用 CUP SDK(CUP 就是 China Union Pay)等第三方的 SDK。另外一种就是使用 iOS 的 PassKit Framework 和银联的接口来接入。本质上来说,...

背锅侠
2016/02/23
79
0
多平台开发库:tbox_v1.4.7_rc1 发布!

TBOX是一个用c语言实现的多平台开发库,支持 windows、linux、mac、ios、android 以及其他嵌入式系统。 针对各个平台,封装了统一的接口,简化了各类开发过程中常用操作,使你在开发过程中,...

ruki
2014/08/15
3.6K
23
C 语言实现的跨平台开发库--TBOX

简介 TBOX 是一个用 C 语言实现的跨平台开发库。 针对各个平台,封装了统一的接口,简化了各类开发过程中常用操作,使你在开发过程中,更加关注实际应用的开发,而不是把时间浪费在琐碎的接口...

ruki
2014/08/15
10.7K
6
TBOX v1.5.0 发布,轻量级跨平台开发库

TBOX v1.5.0 发布,此版本更新内容如下: 更新: 重建整个编译架构,采用xmake跨平台自动构建工具进行构建。。 优化.pkg的依赖包机制,支持依赖库和接口的自动检测,针对libc、libm优先使用自...

ruki
2015/10/22
3K
2

没有更多内容

加载失败,请刷新页面

加载更多

下一页

CentOS “Destination Host Unreachable”问题解决办法

挑战极速安装CentOS时遇到局域网主机不能通信的情况: [root@zjd network-scripts]# ping 8.8.8.8PING 8.8.8.8 (8.8.8.8) 56(84) bytes of data.64 bytes from 8.8.8.8: icmp_seq=1 ttl=......

wffger
4分钟前
0
0
CentoOS6.6安装netcat

CentOS下安装netcat 使用zookeeper过程中,需要监控集群状态。在使用四字命令时(echo conf | nc localhost 2181),报出如下错误:-bash: netcat: command not found。 我的系统是CentOS 6....

ghou-靠墙哭
14分钟前
0
0
es6之解构赋值巧用

ES6 允许按照一定模式,从数组、对象等中提取值,对变量进行赋值,这被称为解构赋值。 如何进行解构赋值我这里就不赘述,本篇文章主要是将解构赋值的巧妙使用之处。 1、交互变量的值 常用交互...

秋季长青
20分钟前
0
0
Elasitcsearch High Level Rest Client学习笔记(三)批量api

Bulk Request BulkRequest可以在一起从请求执行批量添加、更新和删除,至少需要添加一个操作 BulkRequest request = new BulkRequest(); //创建BulkRequestrequest.add(new IndexRequest("...

木子SMZ
23分钟前
0
0
mybatis-dynamic sql

OGNL expressions if 判断是否存在值 <select id="findActiveBlogLike" resultType="Blog"> SELECT * FROM BLOG WHERE state = ‘ACTIVE’ <if test="title != null"> AND title like #{tit......

writeademo
30分钟前
0
0
社交系统ThinkSNS+ V1.8.3更新播报

     研发发布版本号:1.8.3   本次版本于2018年7月16日发布   本次发布类型:新增功能、细节调整与优化   社交系统ThinkSNSPlus更新体验:请于官网下载/安装最新版或联系QQ35159...

ThinkSNS账号
34分钟前
0
0
教育思考:选择编程是一场父母和孩子的和解[图]

教育思考:选择编程是一场父母和孩子的和解[图]: 之前有个很热的段子是这样讲的:深夜十点的时候,某小区一女子大声喊叫“什么关系?啊?!到底什么关系?你说!”最后发现原来是一位妈妈陪...

原创小博客
34分钟前
0
0
X64汇编之指令格式解析

最近由于项目组内要做特征码搜索的东西,便于去Hook一些未导出函数,你懂得...于是就闲着学习了一下x86/x64的汇编指令格式。x86的汇编指令格式请参照http://bbs.pediy.com/showthread.php?t...

simpower
37分钟前
0
0
rust 语法概要(只适合不熟悉时快速查阅使用,不适合理解其精髓。未完待续)

注意:本内容只适合快查,不适合理解精髓。精髓请研读 https://kaisery.github.io/trpl-zh-cn/foreword.html 基本数据类型 i8,i16,i32,i64,i128 u8,u16,u32,u64,u128 f32,f64 char bool:true...

捍卫机密
40分钟前
0
0
JS中严格模式和非严格模式

1,使用 严格模式的使用很简单,只有在代码首部加入字符串 "use strict"。必须在首部即首部指其前面没有任何有效js代码除注释,否则无效 2.注意事项 (1)不使用var声明变量严格模式中将不通...

AndyZhouX
41分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部