redis-lzf压缩算法

文件

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

1
2
3
4
5
6
7
8
/*
* 索引到非压缩字符串前一个字节,将其长度写进该地址
* 如果此压缩字符串前也是压缩字符串,则回溯前一个字节
* 例如000LLLLL和0000LLLL0000
*/
op [- lit - 1] = lit - 1; /* stop run */
op -= !lit; /* undo run if length is zero */
1234567
  • 片段2
1
2
3
4
5
6
7
/*
* 允许程序员将最有可能执行的分支告诉编译器;减少指令跳转
*/
expect_false(expr)
expect_true(expr)
__builtin_expect(EXP, N)
123456
  • 片段3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
有三个点需要说明一下:
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/*
* 获取集中在的长度
* 根据保存的偏移量,获取引用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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
这里需要注意的是:
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
-------------本文结束 感谢阅读-------------