备忘录——压缩整数及其解压缩

迈不过友情╰ 2021-12-10 08:07 297阅读 0赞

# 备忘录——压缩整数及其解压缩 #

原创：[Anders Liu][]

**本文已过时，请参见《.NET/CLI元数据中使用的压缩整数》：[http://www.cnblogs.com/AndersLiu/archive/2010/02/09/compressed-integer-in-metadata.html][http_www.cnblogs.com_AndersLiu_archive_2010_02_09_compressed-integer-in-metadata.html]。**

摘要：.NET/CLI的PE文件中广泛采用了一种整数压缩算法，这种算法可以将一个32位无符号整数根据其大小放置在1、2或4个字节中。本文介绍了这种压缩算法，并给出了解压缩的参考实现。

## 参考文献 ##

ECMA-335——Common Language Infrastructure (CLI) 4th Edition, June 2006

## 简介 ##

本文介绍的整数压缩算法针对的是0x00000000~0x1FFFFFFF之间的32位无符号整数，将这些整数划分成了3个区间\[0x00000000~0x0000007F\]、\[0x00000080~0x00003FFF\]、\[0x000040000~0x1FFFFFFF\]，分别用1、2和4个字节存放。大于0x1FFFFFFF的32位无符号整数不适合用该算法压缩。

该算法广泛应用在.NET/CLI PE文件中，例如各种元数据签名、\#Blob和\#US流等。使用概算法的目的是减小磁盘文件的大小和降低带宽开销，因为.NET程序集的目标是通过网络运行。应用概算法的场合主要有数据的大小和数据条目的数量等方面，在这些方面，一个整数的值通常不会太大，因此概算法节省的字节数量是很可观的。

## 压缩算法描述 ##

*  当整数的大小在0x00000000 (00000000 00000000 00000000 00000000B)到0x0000007F (00000000 00000000 00000000 01111111B)之间时，采用1个字节存放整数值，该字节最高位为0。压缩后的值形如\[0bbbbbbb\]B。
 *  当整数的大小在0x00000080 (00000000 00000000 00000000 10000000B)到0x00003FFF (00000000 00000000 00111111 11111111B)之间时，采用2个字节存放整数值，第一个字节的最高位为1，第二位为0。压缩后的值形如\[10bbbbbb bbbbbbbb\]B。
 *  当整数的大小在0x00004000 (00000000 00000000 01000000 00000000B)到0x1FFFFFFF (00011111 11111111 11111111 11111111B)之间时，采用4个字节存放整数值，第一个字节的最高位和第二位是1，第三位是0。压缩后的值形如\[110bbbbb bbbbbbbb bbbbbbbb bbbbbbbb\]B。
 *  该压缩算法采用大尾数法，即第一个字节是原整数的最高一个字节。

图1更为直观地展示了区间的划分。

图1 - 整数压缩算法

![图1 - 整数压缩算法][1 -]

## 解压缩算法描述 ##

*  如果读到的第一个字节b0型如0bbbbbbb（与0x80进行按位与运算，结果为0x00），则采用1个字节存放整数值。原整数值=b0。
 *  如果读到的第一个字节b0型如10bbbbbb（与0xC0进行按位与运算，结果为0x80），则采用2个字节存放整数值，需要再读取1个字节b1。原整数值=(b0 & 0x3F) << 8 | b1。
 *  如果读到的第一个字节b0型如110bbbbb（与0xD0进行按位与运算，结果为0xC0），则采用4个字节存放整数值，需要再读取3个字节b1、b2、b3。原整数值=(b0 & 0x1F) << 24 | b1 << 16 | b2 << 8 | b3。

## 解压缩算法参考实现 ##

清单1 - 解压缩算法参考实现（C\#描述）

public static UInt32 Decompress(this Byte\[\] data) \{ if (data == null) throw new ArgumentNullException("data"); if (data.Length == 0) throw new InvalidCompressedIntegerException(); if ((data\[0\] & 0x80 /\* (1000000B) \*/) == 0 // 使用一个字节存储大小（0bbbbbbb B) && data.Length == 1) \{ return (UInt32)data\[0\]; \} else if ((data\[0\] & 0xC0 /\* (11000000B) \*/) == 0x80 /\* (10000000B) \*/ // 使用两个字节存放大小（10bbbbbb bbbbbbbb B) && data.Length == 2) \{ return (UInt32)((data\[0\] & 0x3F /\* (00111111B) \*/) << 8 | data\[1\]); \} else if ((data\[0\] & 0xE0 /\* (11100000B) \*/) == 0xC0 /\* (11000000B) \*/ // 使用四个字节存放大小（110bbbbb bbbbbbbb bbbbbbbb bbbbbbbb B） && data.Length == 4) \{ return (UInt32)((data\[0\] & 0x1F /\* (00011111B) \*/) << 24 | data\[1\] << 16 | data\[2\] << 8 | data\[3\]); \} else \{ throw new InvalidCompressedIntegerException(); \} \}

EOF.

转载于:https://www.cnblogs.com/AndersLiu/archive/2008/08/21/compressed-integer.html

[Anders Liu]: http://andersliu.cnblogs.com/
[http_www.cnblogs.com_AndersLiu_archive_2010_02_09_compressed-integer-in-metadata.html]: http://www.cnblogs.com/AndersLiu/archive/2010/02/09/compressed-integer-in-metadata.html
[1 -]: /images/20211210/5759b0f1ca0948d38e445540d150581b.png