Skip to content
This repository has been archived by the owner on Feb 12, 2022. It is now read-only.

Latest commit

 

History

History
59 lines (38 loc) · 5.04 KB

ReadMe (Chinese).md

File metadata and controls

59 lines (38 loc) · 5.04 KB
Raw

LEB128

LEB128 (Little Endian Base 128) 是一种整数二进制编码及压缩方法。有别于传统 32 位或 64 位整数，LEB128 使用不定长格式。因此 LEB128 可以存储理论上任意大小的整数，并且在存储较小的整数时不需要占用全部 32 位或 64 位空间以避免存储空间浪费。

LEB128 与 MIDI 等标准中的 VLQ (Variable-Length Quantity) 使用相同的表达（压缩）方式，只是有效位（有效字节）的顺序不同。在某些编程语言和标准格式中，LEB128 也称七位编码整数 (7-bit Encoded Integer)。

LEB128 编码的基本步骤是将一个整数的常规二进制表示以每 7 位（比特）分割，分别保存在每个字节（8 位）中，然后使用每个字节的第 8 位表示是否需要占用下一个字节。

零和正整数 (Unsigned LEB128)

无符号正整数 624485 编码示例：

步骤 高位 ← 低位 字节流顺序
① 转换为二进制表示 1001 1000 0111 0110 0101
② 高位补 0 以使总位数为 7 的倍数 0 1001 1000 0111 0110 0101
③ 以 7 位分割 010 0110 000 1110 110 0101
④ 高位字节第 8 位上置 0，表示结束编码 0010 0110 000 1110 110 0101
⑤ 剩余字节第 8 位上置 1，表示继续编码 0010 0110 1000 1110 1110 0101
⑥ 自低位字节开始保存并传输数据 0x26 0x8E 0xE5 ←

因此，624485 的 LEB128 编码字节流为 E5 8E 26。基于同样规则，0 的 LEB128 编码字节流为空字节 00。

负整数 (Signed LEB128)

对于有符号（正负号）整数，如果为 0 或正整数，编码步骤和结果与无符号整数完全相同。

负数 −123456 编码示例：

步骤 高位 ← 低位 字节流顺序
① 将绝对值 123456 转换为二进制 1 1110 0010 0100 0000
② 高位补 0 以使总位数为 7 的倍数 0 0001 1110 0010 0100 0000
③ 取反（求绝对值的 1 补码） 1 1110 0001 1101 1011 1111
④ 加 1（求绝对值的 2 补码） 1 1110 0001 1101 1100 0000
⑤ 以 7 位分割 111 1000 011 1011 100 0000
⑥ 高位字节第 8 位上置 0，表示结束编码 0111 1000 011 1011 100 0000
⑦ 剩余字节第 8 位上置 1，表示继续编码 0111 1000 1011 1011 1100 0000
⑧ 自低位字节开始保存并传输数据 0x78 0xBB 0xC0 ←

因此，−123456 的 LEB128 编码字节流为 C0 BB 78。

LEB128.Swift

LEB128.Swift 提供可在 Swift 语言中使用的编码、解码函数，以及原生以 LEB128 内存存储的有符号和无符号整数类型。

编解码 (Codec)

LEB128Encoder 和 LEB128Decoder 提供 Swift 整数类型 Int、UInt 等与 LEB128 编码字节流互相转换的函数。

  • 编码时，函数支持任意遵循 BinaryInteger 协议的类型，因此不局限于编码 Swift 语言的标准整数类型；为保证性能，编码函数默认返回 ContigousArray<UInt8>，如有需要可通过其构造其他数据类型。当 Foundation 模块可用时，编码函数提供返回值为 Data 的扩展。
  • 解码时，函数支持任意元素为 UInt8 的 Collection，包括但不限于 Data 和 [UInt8]。解码函数返回平台无关的 Swift 标准整数类型 Int? 和 UInt?；如果解码的数据超出当前平台下的定长整数长度（例如 64 位），则返回 nil。此时需要通过无长度限制的七位编码整数类型处理数据。

七位编码整数 (7-bit Encoded Integers)

Signed7BitEncodedInteger、Unsigned7BitEncodedInteger 以及协议 SevenBitEncodedInteger 定义了内部以原生 LEB128 字节流存储的有符号和无符号整数类型。这些类型在数据不超出当前平台下的定长整数长度（例如 64 位）时可以与 Swift 标准整数类型互相转换；长度超出时，这些类型仍然提供计算和编解码能力，但无法输出 Int、UInt 和人类可读的十进制表示形式。

目前，Signed7BitEncodedInteger 和 Unsigned7BitEncodedInteger 支持的数学计算仍在拓展。计划最终使它们遵循 BinaryInteger 协议。