复合文档学习笔记（四）

目录及目录流

原创：弄潮小狮

通过前面的讲述，我们已经知道了复合文档如何对存储空间进行管理，这是远远不够的，我们不仅要知道复合文档中的数据，更要知道这些数据表达什么？又如何管理？

这就是本篇要讲述的“目录及目录流”，这也需要先整理几个概念：

目录：如果说，分区表是一份复合文档的物理地图的话，那么，目录就是一份“逻辑地图”，它将告诉我们，在符合文档中的流是如何被组织、被使用的，以及流的存储位置、大小等等。

目录流：前面讲过，目录流是用来储存目录的流，由复合文档直接管理。

目录树：从DOS时代过来的朋友对“目录树”应该不会陌生，没见过DOS的朋友，也有比较直观的学习途径，在Windows下面，有“文件夹”（其实就是DOS的“目录”），文件夹里面又包含文件夹、文件，这就形成了一个树形结构，从“根”到“枝”、“叶”。

红黑树：事实上，我不记得上学的时候学过这个概念（或者说“数据结构”），在此之前连听都没听说过，资料显示，“红黑树”早在1978年已经面世，也许是我上学不认真所致，惭愧！因此，在学习复合文档的时候，我又不得不花了不少时间“恶补”一课（这是我碰到的另一只拦路虎）。要详细讲述这个概念以及实现方法等等，可能会需要很长的篇幅，但简单地说，红黑树是二叉树的一种，有兴趣（或者有需要）的朋友可以自己找资料了解，在网上，这方面的资料不少。

目录入口：英文原文“Directory Entry”，一个说明目录及其相关信息的结构。

既然目录流由复合文档直接管理，那么，如何读取目录流？

根据前面几节的描述，在头部可以找到目录流的第一个扇区的编码（ID）（见：《复合文档学习笔记（二）》图1），根据该编码，从分区表（SAT）中可以读取目录流的扇区链，见图3：

图3

按照目录流的扇区链的顺序，读取每个扇区的数据，“串起来”就是目录流了。

每个目录入口有128（80h）个字节，一个复合文档至少必须有一个目录（即“根入口”，Root Entry），在默认情况下，它大于短扇区尺寸（2^6），因此，目录流总是以扇区来存储。

实际上，不管短扇区尺寸如何设置，目录流不可能以短扇区来存储，这个问题本文最后会谈到。

示例中读出的目录流数据见图4：

图4（WinHex截图）

从图4可以看到，目录流按每128个字节一个目录入口按顺序存放，以第一个目录入口为例，在128个字节的目录信息中：

0（00h）至63（3Fh）共64个字节，存放目录入口名称，采用Unicode字符，是一个0值字符终止的字符串。

64（40h）至65（41h）共2个字节，是一个16位整数，表示目录入口名称的长度（包括终止符0）。

第66（42h）字节，是一个8位整数，表示目录入口的类型：

1（01h）表示目录是一个仓（这个“仓”有点怪，英文原文为“storage”，我想可以理解为相当于一个文件夹）；

2（02h）表示目录是一个流；

5（05h）表示目录是根，在复合文档，通常有且仅有一个这样的目录，并且总是第一个，我不知道有没有例外，在我学习的过程中未确实碰到例外的情况。

其他值，英文原文语焉不详，我在学习过程中也没碰到过，这里不做描述，以免以讹传讹。

第67（43h）字节，是一个8位整数，表示目录入口节点在红黑树中的颜色：0（00h）表示红色，1（01h）表示黑色。

68（44h）至79（4Fh）共12个字节，是三个32位整数，这三个整数的前两个被应用于红黑树中，按顺序分别表示左孩子的目录编码和右孩子的目录编码，值为-1（FFFFFFFFh）时表示该节点为“叶子”，这个请借助红黑树相关理论进行理解，这里不再赘述。第三个整数表示子目录红黑树的根节点，值为-1（FFFFFFFFh）时表示没有子目录（通常流目录入口这个值为-1），这个有点绕，后面专门讲一下。

80（50h）至99（63h）共20个字节，英文原文未做详细解释，并且可以全0，在生成复合文档时，我将其全部填0，未出现异常，权且当作它们是保留字节。

100（64h）至115（73h）共16个字节，是两个8个字节的时间戳，前者表示目录创建的时间，后者表示目录最后修改的时间。关于时间戳，英文原文有详细解释，并有生动示例，这里不再赘述。

116（74h）至119（77h）共4个字节，是一个32位整数，表示目录入口所表示的流的第一个扇区编码（ID），0（00000000h）表示没有。对于根目录，这个值有特殊的含义，本文末尾会有进一步的解释。

120（78h）至123（7Bh）共4个字节，是一个32位整数，表示目录入口所表示的流的尺寸，通过将这个尺寸与短扇区尺寸进行比较，可以确定该流是是以扇区还是短扇区进行存储。

124（7Ch）至127（7Fh）共4个字节，未使用。

示例中的目录入口列表如图5：

图5 

通过上述说明，我们可以整理出示例文件中的目录逻辑结构，见图6：

图6

在这一节中，出现了两种树（红黑树和目录树）及两种根（根目录和根节点），在英文原文中，相关描述语焉不详（或许是小狮的英文实在太烂），在理解上费了不少周折（也是一只不小的拦路虎）。

从图6可以看出，在前面的描述中，红黑树并非目录树的本身的组织形式，目录树只有一棵，它本身就是复合文档中流的组织结构，而红黑树主要用于构造（或查找），每一个仓目录下的子目录独立构成一棵红黑树，上文目录入口中的“子目录红黑树的根节点”说法就变得很好理解了。

查找或遍历目录时，从根目录（Root Entry）开始，从一棵红黑树进入另一棵红黑树，如此往复……

图7是示例文件的目录结构。

图7

另外，从图5可以看到，根目录的“入口扇区”（即“目录入口所表示的流的第一个扇区编码”）有一个值，从前面叙述中，我们已经知道，根目录只是一个特殊的“仓目录”并非是一个“流目录”，它怎么有一个“入口扇区”呢？

这个问题提得好！

在《复合文档学习笔记（三）》中，我介绍了扇区及短扇区，我们必须知道短扇区储存在哪些扇区中，否则无法读取有关数据……

你猜对了，根目录的“入口扇区”就是短扇区所在的扇区的第一个扇区编码，如果一个复合文档中不存在短扇区，那么该值0（00000000h）。

可见，短扇区的偏移量依靠根目录的“入口扇区”来确定，这也是前面讲过“目录流不可能以短扇区来存储”的原因了。

本文很绕舌，因为要讲清楚的目录流跟搞清楚复合文件的目录流一样困难，或许小狮的学习能力及表述能力均有待提高。

学习时脑痛，讲述时也脑痛，但本节终于写完了。

看官就凑合吧！