文件
lzf.h lzfP.h lzf_c.c (压缩) lzf_d.c (解压)
压缩
-
默认模式是VERY_FAST
-
核心思想
- 对重复值进行压缩
- 通过hash表来判断是否重复数据
-
三种模式
| 模式 | （压缩）时间 | （压缩后）空间 |
|---|---|---|
| ULTRA_FAST | 极端快 | 大 |
| VERY_FAST | 非常快 | 中 |
| 普通 | 快 | 小 |
-
变量
LZF_HSLOT_BIAS 64位系统，是in_data的起始地址 ip 输入游标 op 输出游标 hval 整型，当前游标的4位数值ip[-1]|ip[0]|ip[1]|ip[2] htab 保存输入数据(in_data)的下标 hslot 哈希槽，指向哈希表(htab)的指针 ref 值引用，ref = *hslot + LZF_HSLOT_BIAS，也是引用in_data的数据 off 偏移量，ip相对于ref的偏移量 lit literal，非压缩字符串长度
-
流程图
-
代码段
-
片段1
/*
* 索引到非压缩字符串前一个字节，将其长度写进该地址
* 如果此压缩字符串前也是压缩字符串，则回溯前一个字节
* 例如000LLLLL和0000LLLL0000
*/
op [- lit - 1] = lit - 1; /* stop run */
op -= !lit; /* undo run if length is zero */
1234567
- 片段2
/*
* 允许程序员将最有可能执行的分支告诉编译器；减少指令跳转
*/
expect_false(expr)
expect_true(expr)
__builtin_expect(EXP, N)
123456
- 片段3
/*
有三个点需要说明一下：
1、长度小于7，偏移量的高5位保存在op[0]低5位；长度保存在高三位
2、大于等于7，偏移量的高5位保存在op[0]低5位；7(111)保存在高三位。长度减去7保存在op[1]
3、剩余的偏移量低8位，保存在op[2]
*/
if (len < 7)
{
*op++ = (off >> 8) + (len << 5);
}
else
{
*op++ = (off >> 8) + ( 7 << 5);
*op++ = len - 7;
}
*op++ = off;
1234567891011121314151617
| 5b | 3b/11b | 8b |
|---|---|---|
| off高5位 | len | off低8位 |
-
例子
| 原始数据 | 压缩后数据 |
|---|---|
| 0 | 00 30 |
| 00 | 01 30 30 |
| 000 | 02 30 30 30 |
| 000L | 03 30 30 30 4C |
| 000LL | 04 30 30 30 4C 4C |
| 000LLL | 05 30 30 30 4C 4C 4C |
| 000LLLL | 03 30 30 30 4C 20 00 |
| 000LLLLL | 03 30 30 30 4C 20 00 00 4C |
解压
-
流程图
-
代码段
-
片段1
/*
* 获取集中在的长度
* 根据保存的偏移量，获取引用ref
*/
unsigned int len = ctrl >> 5;
u8 *ref = op - ((ctrl & 0x1f) << 8) - 1;
#if CHECK_INPUT
if (ip >= in_end)
{
SET_ERRNO (EINVAL);
return 0;
}
#endif
if (len == 7)
{
len += *ip++;
#if CHECK_INPUT
if (ip >= in_end)
{
SET_ERRNO (EINVAL);
return 0;
}
#endif
}
ref -= *ip++;
12345678910111213141516171819202122232425262728
- 片段2
/*
这里需要注意的是：
ref是op的引用，也就是输出数据的引用；因此也就是数据的自我复制。
*/
case 9: *op++ = *ref++; /* fall-thru */
case 8: *op++ = *ref++; /* fall-thru */
case 7: *op++ = *ref++; /* fall-thru */
case 6: *op++ = *ref++; /* fall-thru */
case 5: *op++ = *ref++; /* fall-thru */
case 4: *op++ = *ref++; /* fall-thru */
case 3: *op++ = *ref++; /* fall-thru */
case 2: *op++ = *ref++; /* fall-thru */
case 1: *op++ = *ref++; /* fall-thru */
case 0: *op++ = *ref++; /* two octets more */
*op++ = *ref++; /* fall-thru */
123456789101112131415