备忘录——压缩整数及其解压缩
原创：Anders Liu
本文已过时，请参见《.NET/CLI元数据中使用的压缩整数》：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 - 整数压缩算法
解压缩算法描述
- 如果读到的第一个字节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.
