lz4帧格式描述

LZ4帧格式描述

译者注

  • 撰写qkafkaclient(Qt实现的Kafka Client时)使用到了这个压缩算法,于是翻译此文档,限于翻译水平,如有理解不了的地方请参照原文
  • Kafka中使用的LZ4帧格式java实现与此文档描述以及原版C++实现有些出入,我在译文中会着重指出,并标记。
  • 欢迎转载,注明出处即可,同时欢迎访问我的blog,谢谢。

注意事项

版权所有 (c) 2013-2015 Yann Collet

此文档允许任何目的免费复制和传播,包括翻译成其他语言以及编入其他的书籍和文档,只需将此版权声明和注意事项保留,并将对原文的任何修改和删除清晰标注出来即可。
分发此文档无任何限制。

Permission is granted to copy and distribute this document
for any purpose and without charge,
including translations into other languages
and incorporation into compilations,
provided that the copyright notice and this notice are preserved,
and that any substantive changes or deletions from the original
are clearly marked.
Distribution of this document is unlimited.

版本

1.5.1 (31/03/2015)

介绍

此文档的目的是定义一种无损压缩的数据格式,与CPU类型,操作系统,文件系统以及字符集无关,适用于使用LZ4算法的文件压缩,管道以及流压缩。

数据可以被生产或者消费(即使对于任意长顺序给出的输入数据流)时,都只需使用一定先验量的中间存储,因此可以被用作数据通讯领域。
该格式使用LZ4压缩算法,以及可选xxHash-32校验和算法作为数据完整性校验。

本规范所定义的数据格式并不试图允许随机访问压缩数据。

本规范适用于软件开发者压缩和解压缩LZ4格式的数据。本规范的内容假定读者拥有一些基本的关于比特和其他原始数据表达的基本编程背景。

除非另有说明,一个兼容的压缩软件必须产生符合这份说明提出的规范的数据集。但不比实现所有可选项。

一个兼容的解压缩软件必须能够解压缩至少能够解压缩此规范提出的一种参数的工作集。它可以忽略校验和。当它不能够支持压缩刘中的某种特定参数时,他必须返回一个明确的错误代码,通过此错误代码能够关联到哪个参数未被支持的错误信息。

LZ4帧格式的一般结构

帧起始字节(MagicNb) 帧描述 (…) 结束标记 内容校验和
4 字节 3-11 字节 4 字节 4 字节

帧起始字节(Magic Number)

4 字节, 小端格式.
值 : 0x184D2204

帧描述

3 to 11 字节, 后文详细描述.
本规范最重要的部分.

数据块(复数,可能有多个)

后文描述。这些是压缩数据存储的地方。

结束标记(End Mask)

当最后一个数据块大小为“0”时,数据块流就结束了。
数据块大小用一个32位整数值表示。

内容校验和(Content checksum)

内容校验和检验整个解压缩的内容是否正确。内容的校验和是对原始(解压缩)数据为输入,种子(seed)为0的xxh32()哈希算法的结果。
内容校验和只当帧描述中的标记位设置时才会有。内容校验和保证了所有的数据块被完整、按顺序且正确传输,并且压缩/解压缩过程本身不产生失真。建议您使用它

帧连结

在某些情况下,可能需要连结多个帧,比如为了添加薪的数据到已存在的一个压缩文件末尾,而不希望重新打包帧时。

这种情况下,每个帧拥有自己的帧描述标记。每个帧被认为是独立的。帧间唯一的关系是他们的顺序。

解压缩单个文件或者流中的多个连续的帧不在此规范中描述。作为一个例子,LZ4命令行程序的做法就是按顺序对所有连续帧进行解码。

帧描述(Frame Descriptor)

标记 BD (内容长度) 头校验和
1 byte 1 byte 0 – 8 bytes 1 byte

根据可选的参数,帧描述至少3位长度,最多11位长度。

标记位字节

7-6 5 4 3 2 1-0
名称 版本 块独立标志位 块校验位 内容长度位 内容校验位 保留

BD byte

7 6-5-4 3-2-1-0
名称 保留 块最大长度 保留

表中,第7位位最高位,第0位为最低位。

版本号

2位字段, 必须被设置为 “01”.
任何其他的值都不能被此版本的规范解压缩。其他版本号将会使用不同的标记位布局。

块独立标记位(Block Independence flag)

如果此标记位设置为“1”,那么块与块之间独立的。
如果次标记位设置为“0”,那么每个块都会依赖于其前面的块(最多64KB,基于LZ4窗口大小)。
此种情况下,就必须按顺序解压缩所有的块。

数据块的依赖性会提高压缩率,尤其对于小数据块而言。但同时,也使得直接跳过数据块,以及多线程解压缩不可行。

注:Kafka中只支持块相互独立(此标记=1)

块校验和标记

如果此标记被设置,每个数据块将会跟一个4字节的校验和,该值使用xxHash-32算法对数据块数据(压缩后的)进行计算得到。
此校验和是为了在解压缩前能够立即检验数据的完整性(有无存储或者传输错误)。快校验的使用是可选项。

内容大小标记

如果该标志被设置时,将会存在一个8字节无符号的小端整数,作为此帧中未压缩数据的尺寸。内容大小的使用是可选的。

内容校验和标记

如果此标记被设置,那么内容校验和将会被附加在结束标记(EndMark)后。

建议值:”1”(存在内容校验和)

数据块最大长度(Block Maximum Size)

此信息用来帮助解压缩器分配内存。这里尺寸指的是原始(未压缩)的数据大小。块最大尺寸为下表中的一个值

0 1 2 3 4 5 6 7
N/A N/A N/A N/A 64 KB 256 KB 1 MB 4 MB

解压缩器可能拒绝分配超过一定大小(与系统相关)的块大小。未使用的值可能会被将来版本的规范使用。
符合当前版本规范的解压缩器只能解压缩这个版本规定的块大小(blocksize)。

预留位

预留字段的值必须为0(zero)。
保留位可能会在规范的未来版本中使用,通常支持新的可选功能。
如果发生这种情况,遵循当前版本规范的解压缩器不应能够解码这种帧。

内容大小

这是原始数据(未压缩)的大小。这个信息是可选的,并且仅当相关标志被设置时存在。
此值使用8字节无符号整数,最大为16艾字节(HexaBytes),小端格式。
此信息,通常用于显示或者内存分配。解压缩器可以忽略它,或用于验证内容的正确性。

头校验和(Header Checksum)

帧头部描述符字段,包括可选字段部分的校验和,一个字节。值为将整个帧描述作为输入(包含存在的可选字段),0作为种子,使用xxh32()方法计算结果中的第二个字节:(xxh32()>>8) & 0xFF
一个错误的校验和意味着帧描述存在错误。头校验和仅做为信息用(informational),可以忽略。

注:Kafka中使用整个头部信息作为校验和输入(包含Magic Number)

数据块(Data Blocks)

块大小 数据 (块校验和)
4 bytes 0 – 4 bytes

块大小

此字段为4字节整数,小端格式。

如果数据没有被压缩,那么最高位为“1”。
如果数据被LZ4算法压缩,那么最高位为“0”。
所有其他位给出下一个数据块尺寸,单位为字节(如果存在块校验和,那么该大小不包括块校验和)。

块尺寸应该不会大于块最大尺寸(Block Maximum Size)。但对于未压缩的元数据,这样的事情可能发生。这种情况下,这样的数据块必须以未压缩格式传递。

数据

待解码的实际数据所在。
基于前面一个字段的标记,它可能被压缩的或者未被压缩的。
未压缩的数据长度可能为任意长度,超过“块最大大小”(block maximum size)。
注意,数据块不一定是满的:任意的“刷新”随时可能发生。任何块都可能被“部分填充”。

块校验和(Block checksum)

只有当相关的标志位被设置时存在。这是一个4字节的校验值,以小端格式保存,以0为种子计算原始数据(未解压缩)的xxHash-32值得到。
以便在解压缩前检测数据是否完整(是否存在存储或传输错误)

Block checksum is cumulative with Content checksum.

可跳过的帧(Skippable Frames)

帧头标志 帧大小 用户数据(UserData)
4 bytes 4 bytes

可跳过帧允许用户整合一些用户自定义数据到连续的数据帧中。
它的设计非常简单,以便解压缩器能够快速跳过用户自定义数据从而继续解压缩。
为了便于识别的目的,我们不推荐用一个可跳过帧来开始一个连续的帧流。如果的确有需要用一些包装在可跳过帧中的用户数据,那么建议以一个0字节的LZ4帧开始,然后跟上一个可跳过帧。这样可以方便文件类型识别器。

帧头标志(Magic Number)

4 字节, 小端格式。
值 : 0x184D2A5X, 代表任何从 0x184D2A50 到 0x184D2A5F 的值。
所有16个值都可以有效的标识可跳过帧。

帧大小(Frame Size)

这是随后的用户数据的大小(不包括帧头标志及帧大小字段本身),字节位单位。
4字节小端无符号数。意味着用户数据不能大于2^32-1字节。

用户数据(User Data)

用户数据可以是任何东西。数据将被解压缩器跳过。

历史遗留的帧格式(Legacy frame)

(已经不再使用,故不再翻译了,需要了解的请从原文链接过去看)

版本变化(Version changes)

1.5.1 : 文档格式兼容MarkDown

1.5 : 从规范中去掉字典ID(Dictionary ID)

1.4.1 : 更改措辞, 变“stream” 为 “frame”

1.4 : 添加可跳过流(帧),重新添加流(帧)校验和

1.3 : 修改头部校验和

1.2 : 减少“块大小”的选项,推迟对“块大小字段的动态大小”(“dynamic size of BlockSize Field”)的决定。.

1.1 : 可选字段现在描述符的一部分。

1.0 : 变“块大小”规范,增加了压缩/非压缩标志。

0.9 : 减少“块最大尺寸”表的规模

0.8 : 去掉 : 高压缩标志

0.7 : 去掉 : 流(帧)校验和

0.6 : 敲定 : 流(帧)大小为8字节, 使用小端

0.5: 添加版权注意事项

0.4 : 改变格式文件格式为Google Doc兼容的OpenDocument。

来源: https://raw.githubusercontent.com/Cyan4973/lz4/master/lz4_Frame_format.md

发表评论

电子邮件地址不会被公开。 必填项已用*标注