3.7　数据的打包和解包

打包数据的优点是能够高效地利用内存。以美国的社会安全号码（SSN，Social Security number）为例，它是下面这种形式的9位标识代码（一个X代表一个十进制数字）：

采用3个独立整型（32位）编码的SSN需要12个字节。这比使用字符串数组表示还要多一个字节。更好的解决方案是使用短整型（16位）对每个字段进行编码，这样只需要6个字节就可以表示SSN。而SSN中间字段的值始终都在0～99，因此实际上中间字段的编码只需要一个字节，这样整个数据结构可以再减少一个字节。下面的Free Pascal/Delphi记录结构就是这种数据结构：

如果不考虑连字符，SSN就是一个9位的十进制数。30位就可以精确地表示全部的9位十进制数，因此可以使用32位整型对任意合法的SSN进行编码。但是，有些处理SSN的软件可能需要操作单独的字段。这意味着从32位整型格式的SSN编码中提取字段会用到代价更高的除法、模和乘法运算。此外，使用32位格式时，字符串和SSN之间的转换也会更复杂。

相反，使用快速的机器指令插入和提取单个位字段很简单，而且创建这些字段的标准字符串表示形式（包括连字符）所需的工作量也较少。图3-8展示了SSN打包数据类型的简单实现，每个字段使用一个单独的位串（注意，这种格式只用到了31位，忽略了高位）。

访问打包数据对象中从0位开始排列的字段是最高效的，因此，应该把最常访问的字段 从第0位开始排列。如果无法判断哪个字段最常访问，就从字节边界开始排列这些字段。如果打包类型中存在没有用到的位，则可以把这些空位分散到整个结构中，让各个字段从字节边界开始排列，让它们以8位为单位排列。

图3-8中的SSN例子中只有一个没有用到的空位。但事实上我们可以利用这个多出来的空位让两个字段和字节边界对齐，以确保这些字段中有一个的位串长度是8位的倍数。图3-9展示了一种重新排列的SSN数据类型版本。

图3-9中的数据格式有一个问题是，不能通过比较32位无符号整型直接对SSN排序 。如果需要进行大量基于SSN的排序，则图3-8中的格式可能会更好。

如果排序不重要，那么图3-9中的格式优点更多。这种打包类型实际上使用了8位（而不是7位）来表示SecondField（而且SecondField从第0位开始排列），多出来的一位总是0。也就是说SecondField占用了第0～7位（一个字节），而ThirdField正好从字节边界开始（第8位）。ThirdField占用的位数并不是8的倍数，而FirstField也不是从一个字节边界开始排列，但考虑到只有一位可以填充，这种编码的效果还不错。

接下来的问题是，如何访问这种打包类型中的字段？其中有两种独立的操作。既需要获取或提取（Extract）打包好的字段，也需要向这些字段中揑入（Insert）数据。AND、OR和SHIFT运算就是我们的工具。

当操作这些字段时，使用三个独立的变量比直接使用打包数据更方便。以SSN为例，我们可以创建三个变量：FirstField、SecondField和ThirdField，然后将打包的实际数据提取到这三个变量中，再对这些变量进行操作，最后将变量中的数据插回到对应的字段中。

要提取图3-9所示的打包数据中的SecondField（记住，访问第0位开始的字段是最简单的），需要把打包格式的数据复制到变量SecondField中，然后使用AND运算将SecondField字段以外的位屏蔽掉。因为SecondField是一个7位的值，所以屏蔽使用的掩码的第0～6位都是1，其他位是0。下面这段C/C++代码展示了如何将该字段提取到SecondField变量中（假设 packedValue 是保存打包SSN数据的32位变量）：

如果要提取的不是从第0位开始排的字段，则需要做更多的工作。以图3-9中的ThirdField字段为例。我们可以通过用%_11_1111_1111_1111_0000_0000（$3F_FF00）和打包数据进行AND逻辑运算来屏蔽第一个字段及第二个字段的所有位。但是，ThirdField的值依然还留在第8～21位，进行算术运算并不方便。解决方法是将经过掩码的值向右移动8位，让它在处理的变量中对齐第0位。下面展示的是Pascal/Delphi的做法：

也可以先移动，再执行AND逻辑运算（但使用的掩码不同，为$11_1111_1111_1111或$3FFF）。下面是采用这种方法提取ThirdField的C/C++/Swift代码：

要提取（左边）和高位对齐的字段，比如SSN打包数据类型中的第一个字段，则需要将高位字段向右移动到与第0位（右边）对齐。逻辑右移运算会自动把高位填充为0，因此不需要掩码。下面这段Pascal/Delphi代码展示了高位字段的提取方法：

HLA/x86汇编语言可以方便地访问内存中任何字节边界上的数据。这样我们可以就当数据结构中的第二和第三个字段是和第0位对齐的。而且SecondField是一个8位的值（高位始终为0），因此解包数据只需要一条机器指令，如下所示：

该指令获取 packedValue 的第一个字节（在80x86上就是 packedValue 的低8位），并且在EAX寄存器中将这个值零扩展到32位（movzx代表“移动并零扩展”）。这条指令执行完毕后，EAX寄存器存储的就是SecondField的值。

打包数据类型中ThirdField的位数不是8的偶数倍，所以仍然需要掩码清除32位结果中不会被用到的位。但是打包结构中的ThirdField和字节（8位）边界是对齐的，因此在高级语言中必需的移位操作在汇编语言中可以避免。下面是从 packedValue 对象中提取第三个字段的HLA/x86汇编代码：

从 packedValue 对象中提取FirstField的HLA/x86汇编代码和高级语言代码相同，只需要简单地将高10位（FirstField占用的位）移到第0位：

要把某个变量中的数据插入打包对象，如果变量中没有用到的位都是0，则一共需要执行三个步骤。首先，必要时把字段数据左移，按位来和打包对象中的对应字段对齐。然后，将打包结构中该字段对应的位全部置零。最后，将经过移位的字段和打包对象进行 OR逻辑运算。详细操作如图3-10所示。

下面是实现了图3-10中操作的C/C++/Swift代码：

十六进制值$FFC000FF第8～21位都为0，其余位为1。 SI5U5SHjO38JrKUg2NscDxlbYWaQtq4xTMbmHYtn+RgRK5vogIoMmd6XtrPqlqMN