1. Storages and Streams

复合文档的原理就像一个文件系统（文件系统：如 FAT 与 NTFS ）。复合文档将数据分成许多流（ Streams ），这些流又存储在不同的仓库（ Storages ）里。将复合文档想象成你的 D 盘， D 盘用的是 NTFS （ NT File System ）格式，流就相当于 D 盘里的文件，仓库就相当于 D 盘里的文件夹。流和仓库的命名规则与文件系统相似，同一个仓库下的流及仓库不能重名，不同仓库下可以有同名的流。每个复合文档都有一个根仓库（ root storage ）。

RootStorage

2.Sectors and Sector Chains

2.1 Setctors

整个复合文档被切成一块块sector,在文档头部的结构体中标有每个sector的大小。和第一个sector表的偏移。Sector表存放所有sector的块。(除开Compound Document Header后就是第零块sector。)

| SID | Name | Meaning |
| ---------- |
| 0xFFFFFFFF | Free SID | 空闲 sector ，可存在于文件中，但不是任何流的组成部分 |
| 0xFFFFFFFE | End Of Chain SID | SID 链的结束标记 |
| 0xFFFFFFFD | SAT SID | 此 Sector 用于存放扇区配置表 |
| 0xFFFFFFFC | MSAT SID | 此 Sector 用于存放主扇区配置表 |

2.2 Sector Chains

所有sector存在Sector表中，表头的位置表示SID 0之后就是SID1，SID2......每个位置占4个字节，每个位置存储着下个SID。用于存储流数据的所有 Sectors 的列表叫做扇区链（ Sector Chain ）。这些 Sectors 可以是无序的。因此用于指定一个流的 Sectors 的顺序的 SID 数组就称为 SID chain 。一个 SID chain 总是以 End Of Chain SID （－ 2 ）为结束标记。表示直达 End Of Chain SID (0xFFFFFFFE);

例：一个流由 4 个 Sector 组成，其 SID 链为 [1, 6, 3, 5, –2] 。

SectorChains

3.Compound Document Header

3.1 Header

复合文档头在文件的开始，且其大小必定为 512 字节。这意味着第一个 Sector 的开始相对文件的偏移量为 512 字节。复合文档头的结构如下：

| Offset | Size | Contents |
| ---------- |
|0 | 8 |复合文档文件标识： D0H CFH 11H E0H A1H B1H 1AH E1H|
|8 | 16 |此文件的唯一标识 ( 不重要 , 可全部为 0)|
|24| 2 |文件格式修订号 ( 一般为 003EH)|
|26| 2 |文件格式版本号 ( 一般为 0003H)|
|28| 2 |字节顺序规则标识: FEH FFH = Little-Endian FFH FEH = Big-Endian|
|30| 2 |复合文档中 sector 的大小 (ssz) ，以 2 的幂形式存储 , sector 实际大小为 s_size|
|32| 2 |short-sector 的大小，以 2 的幂形式存储 , short-sector 实际大小|
|34| 10 |Not used|
|44| 4 |用于存放扇区配置表（ SAT ）的 sector 总数|
|48| 4 |用于存放目录流的第一个 sector 的 SID|
|52| 4 |Not used|
|56| 4 |标准流的最小大小 ( 一般为 4096 bytes), 小于此值的流即为短流。|
|60| 4 |用于存放短扇区配置表（ SSAT ）的第一个 sector 的 SID 或为 –2 (End Of Chain SID) 如不存在。|
|64| 4 |用于存放短扇区配置表（ SSAT ）的 sector 总数|
|68| 4 |用于存放主扇区配置表（ MSAT ）的第一个 sector 的 SID|
|72| 4 |用于存放主扇区配置表（ MSAT ）的 sector 总数|
|76| 436 |存放主扇区配置表（ MSAT ）的第一部分，包含 109 个 SID 。|

3.2 Sector Offset

从头中的信息可以计算出一个 sector 的偏移量（ offset ），公式为：
sec_pos(SID) = 512 + SID ∙ s_size = 512 + SID ∙ 2 ssz
例： ssz = 10 and SID = 5:
sec_pos(SID) = 512 + SID ∙ 2 ssz = 512 + 5 ∙ 210 = 512 + 5 ∙ 1024 = 5632.

4.Sector Allocation

4.1 Master Sector Allocation Table

主扇区配置表（ MSAT ： master sector allocation table ）是一个 SID 数组，指明了所有用于存放扇区配置表（ SAT ： sector allocation table ）的 sector 的 SID 。 MSAT 的大小（ SID 个数）就等于存放 SAT 的 sector 数，在头中指明。
MSAT 的前 109 个 SID 也存放于头中，如果一个 MSAT 的 SID 数多余 109 个，那么多出来的 SID 将存放于 sector 中，头中已经指明了用于存放 MSAT 的第一个 sector 的 SID 。在用于存放 MSAT 的 sector 中的最后一个 SID 指向下一个用于存放 MSAT 的 sector ，如果没有下一个则为 End Of Chain SID （ -2 ）。
存放 MSAT 的 sector 的内容：（ s_size 表示 sector 的大小）

| Offset | Size | Contents |
| ---------- |
|0 | s_size － 4 | MSAT 的 (s_size － 4) / 4 个 SID 的数组|
|s_size － 4 | 4 | 下一个用于存放 MSAT 的 sector 的 SID ，或－ 2 （已为最后一个）|

最后一个存放 MSAT 的 sector 可能未被完全填满，空闲的地方将被填上 Free SID(-1) 。

例：一个复合文档需要 300 个 sector 用于存放 SAT ，头中指定 sector 的大小为 512 字节，这说明
sector 可存放 128 个 SID 。 MAST 有 300 个 SID ，前 109 个放于头中，其余的 191 个将要占用 2 个 sector 来存放。此例假定第一个存放 MSAT 的 sector 为 sector 1 ，则 sector 1 包含 127 个 SID 。第 128 个 SID 指向一个用于存放 MSAT 的 sector ，假定为 sector 6 ，则 sector 6 包含剩下的 64 个 SID （最后一个 SID 为－ 2 ，其他的值为－ 1 ）。

4.2 Sector Allocation Table

扇区配置表（ SAT ： sector allocation table ）是一个 SID 数组，包含所有用户流（短流除外）和内部控制流（ the short-stream container stream, the short-sector allocation table and the directory,) 的 SID 链。 SAT 的大小（ SID 个数）就等于复合文档中所存在的 sector 的个数。
SAT 的建立就是通过按顺序读取 MSAT 中指定的 sector 中的内容。
存放 SAT 的 sector 的内容：（ s_size 表示 sector 的大小）

| Offset | Size | Contents |
| ---------- |
|0 | s_size | SAT 的 s_size / 4 个 SID 的数组|

当通过 SAT 为一个流创建 SID 链时， SAT 数组的当前位置（ array index) 表示的就是当前的 sector ，而该位置存放的 SID 则指向下一个 sector 。

SAT 可能在任意位置包含 Free SID （－ 1 ），这些 sector 将不被流使用。如果该位置包含 End Of Chain SID （－ 2 ）表示一个流的结束。如果 sector 用于存放 SAT 则为 SAT SID （－ 3 ），同样用于存放 MSAT 则为 MSAT SID （－ 4 ）。
一个 SID 链的起点从用户流的目录入口（ directory entry ）或头（内部控制流）或目录流本身获得。
例：一个复合文档包含一个用于存放 SAT 的 sector （ sector 1 ）和 2 个流。
Sector 1 的内容如下图：

SAT

在位置 1 其值为－ 3 ，表明 Sector 1 是 SAT 的一部分。
其中一个流为内部目录流，假定头中指定其开始为 Sector 0 ， SAT 中位置 0 的值为 2 ，位置 2 的值为 3 ，位置 3 的值为－ 2 。因此目录流的 SID 链为 [0, 2, 3, –2] ，即此目录流存放于 3 个 sector 中。
目录中包含一个用户流的入口假定为 sector 10 ，从图中可看出此流的 SID 链为 [10, 6, 7, 8, 9, –2] 。

5.Short-Streams

5.1 Short-Stream Container Stream

当一个流的大小小于指定的值（在头中指定），就称为短流 (short-stream) 。
短流并不是直接使用 sector 存放数据，而是内含在一种特殊的内部控制流——短流存放流（ short-stream container stream ）中。

短流存放流象其他的用户流一样：先从目录中的根仓库入口（ root storage entry ）获得第一个使用的 sector ，其 SID 链从 SAT 中获得。然后此流将其所占用的 sectors 分成 short-sector ，以便用来存放短流。此处也许较难理解，我们来打个比方：既然流组成符合文档，而短流组成短流存放流，这两者是相似的。把短流存放流当作复合文档，那么短流对应流， short-sector 对应 sector ，唯一的不同是复合文档有一个头结构，而短流存放流没有。 short-sector 的大小在头中已经指定，因此可根据 SID 计算 short-sector 相对于短流存放流的偏移量（ offset ）。公式为：

short_s_pos(SID) = SID ∙ short_s_size = SID ∙ 2 sssz
例： sssz = 6 and SID = 5:
short_s_pos(SID) = SID ∙ 2 sssz = 5 ∙ 26 = 5 ∙ 64 = 320.

5.2 Short-Sector Allocation Table

短扇区配置表（ SSAT ： short-sector allocation table ）是一个 SID 数组，包含所有短流的 SID 链。与 SAT 很相似。

用于存放 SSAT 的第一个 sector 的 SID 在头中指定，其余的 SID 链从 SAT 中获得。
存放 SSAT 的 sector 的内容：（ s_size 表示 sector 的大小）

| Offset | Size | Contents |
| ---------- |
|0 | s_size |SSAT 的 s_size / 4 个 SID 的数组|

SSAT 的用法与 SAT 类似，不同的是其 SID 链引用的是 short-sector 。

6.Directory

6.1 Directory Structure

目录（ directory ）是一种内部控制流，由一系列目录入口（ directory entry ）组成。每一个目录入口都指向复合文档的一个仓库或流。目录入口以其在目录流中出现的顺序被列举，一个以 0 开始的目录入口索引称为目录入口标识 (DID: directory entry identifier) 。
如下所示：

DIRECTORY ENTRY 0
DIRECTORY ENTRY 1
DIRECTORY ENTRY 2
DIRECTORY ENTRY 3

目录入口的位置不因其指向的仓库或流的存在与否而改变。如果一个仓库或流被删除了，其相应的目录入口就标记为空。在目录的开始有一个特殊的目录入口，叫做根仓库入口（ root storage entry ），其指向根仓库。
目录将每个仓库的直接成员（仓库或流）放在一个独立的红黑树（ red-black tree ）中。红黑树是一种树状的数据结构，本文仅简单介绍一下，详细情况请参考有关资料。
建构一个 Red-Black tree 的规则：

1. 每个节点（ node ）的颜色属性不是红就是黑。
2. 根节点一定是黑的。
3. 如果某个节点是红的，那它的子节点一定是黑的。
4. 从根节点到每个叶节点的路径（ path ）必须有相同数目的黑节点。

ex:     B                ( 用图形来解说第４点，从根节点
     /     /             到最底层的 node ，你会发现每个
    B       B            path 都恰好有３个 black node)
   / /    /   /        
  B   B  R     B
 /      / /   / /
R      B   B R   R
      / /
     R   R

例：以第一章中的图为例

1. 根仓库入口描述根仓库，它不是任何仓库入口的成员，因此无需构建红黑树。
2. 根仓库的所有直接成员 (“Storage1”, “Storage2”, “Stream1”, “Stream2”, “Stream3”, 和 “Stream4”) 将组成一棵红黑树，其根节点的 DID 存放于根仓库入口中。
3. 仓库 Storage1 只有一个成员 Stream1 ， Stream1 构成一棵红黑树，此树只有一个节点。 Storage1 的目录入口包含 Stream1 的 DID 。
4. 仓库 Storage2 包含 3 个成员“ Stream21”, “Stream22”, 和 “Stream23” 。这 3 个成员将构建一棵红黑树，其根节点的 DID 存放于 Storage2 的目录入口中。

这种存放规则将导致每个目录入口都包含 3 个 DID：

1. 在包含此目录入口的红黑树中，此目录入口的左节点的 DID 。
2. 在包含此目录入口的红黑树中，此目录入口的右节点的 DID 。
3. 若此目录入口表示一个仓库，则还包含此仓库的直接成员所组成的另一颗红黑树的根节点的 DID 。
   在构建红黑树的过程中，一个节点究竟作为左还是右，是通过比较其名字来判断的。一个节点比另一个小是指其名字的长度更短，如长度一样，则逐字符比较。
   规定：左节点 < 根节点 < 右节点。

6.2 Directory Entry Structure

一个目录入口的大小严格地为 128 字节，计算其相对目录流的偏移量的公式为： dir_entry_pos(DID) = DID ∙ 128 。
目录入口的内容：

| Offset | Size | Contents |
| ---------- |
|0 |64 |此入口的名字（字符数组） , 一般为 16 位的 Unicode 字符 ,以 0 结束。 ( 因此最大长度为 31 个字符 )|
|64 |2 |用于存放名字的区域的大小，包括结尾的 0 。|
|66 |1 |入口类型 : 00H = Empty 03H = LockBytes (unknown) 01H = User storage 04H = Property (unknown) 02H = User stream 05H = Root storage|
|67 |1 |此入口的节点颜色 : 00H = Red 01H = Black|
|68 |4 |其左节点的 DID ( 若此入口为一个 user storage or stream) 若没有左节点就为－ 1 。|
|72 |4 |其右节点的 DID ( 若此入口为一个 user storage or stream) ， 若没有右节点就为－ 1 。|
|76 |4 |其成员红黑树的根节点的 DID ( 若此入口为 storage), 其他为－ 1 。|
|80 |16 |唯一标识符（若为 storage ） ( 不重要 , 可能全为 0)|
|96 |4 |用户标记 ( 不重要 , 可能全为 0)|
|100 |8 |创建此入口的时间标记。大多数情况都不写。|
|108 |8 |最后修改此入口的时间标记。大多数情况都不写。|
|116 |4 |若此为流的入口，指定流的第一个 sector 或 short-sector 的 SID, 若此为根仓库入口，指定短流存放流的第一个 sector 的 SID, 其他情况，为 0 。|
|120 |4 |若此为流的入口，指定流的大小（字节）若此为根仓库入口，指定短流存放流的大小（字节）其他情况，为 0 。|
|124 |4 |Not used|

参考文献

• Microsoft Compound DocumentFile Format
• 复合文档的二进制存储格式研究