一. 仓库与流

1. 什么是复合文档?

• 复合文档（Compound Document） 是一种不仅包含文本而且包括图形、电子表格数据、声音、视频图象以及其它信息的文档。可以把复合文档想象成一个所有者，它装着文本、图形以及多媒体信息如 声音和图象。目前建立复合文档的趋势是使用面向对象技术，在这里，非标准信息如图像和声音可以作为独立的、自包含式对象包含在文档中。Microsoft Windows就是使用这种技术，叫做“OLE2 storage file format”或“Microsoft Office compatible storage file format”。

• 当然Excel、Word等都是用这种格式存储的。本文主要研究复合文档的二进制结构。

2. 仓库与流

• 复合文档的原理就像一个文件系统（文件系统：如FAT与NTFS）。复合文档将数据分成许多流（Streams），这些流又存储在不同的仓库（Storages）里。将复合文档想象成你的D盘，D盘用的是NTFS（NT File System）格式，流就相当于D盘里的文件，仓库就相当于D盘里的文件夹。

• 关系如下图:
  

二. 扇区与扇区链

1. 扇区与扇区标识

• 所有的流又分成更小的数据块，叫做数据扇区（sectors）。Sectors 可能包含控制数据或用户数据。

• 整个文件由一个头（Header）结构以及其后的所有Sectors组成。Sectors的大小在头中确定，且每个Sectors的大小都相同。

• 大概是这种格式:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

  HEADER (包含下面Sector的个数,大小信息) SECTOR 0 (以下的所有sector大小都一致) SECTOR 1 SECTOR 2 SECTOR 3 SECTOR 4 SECTOR 5 SECTOR 6 ....

• Sectors 简单的以其在文件中的顺序列举，一个扇区的索引（从0开始）叫做扇区标识（SID：sector identifier）。SID是一个有符号的32位的整型值。

• 如果一个SID的值非负，就表示真正存在的那个Sector；如果为负，就表示特殊的含义。下表给出有效的特殊SID：

2. 扇区链与扇区标识链

• 用于存储流数据的所有Sectors的列表叫做扇区链(Sector Chain)。这些Sectors可以是无序的。因此用于指定一个流的Sectors的顺序的SID数组就称为SID chain。一个SID chain总是以End Of Chain SID（－2）为结束标记。

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

三. 复合文档头

1. 复合文档头(Header)

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

• 复合文档头的结构如下：

2. 扇区偏移量计算方法

• sector_pos: 扇区的位置
  
• SID: 扇区的索引
  
• ssz: header中的每个sector大小
  

1

sector_pos[SID] = 9^2 + SID * ssz^2

例：ssz = 10 and SID = 5:

1
2
3

sector_pos[SID] = 9^2 + 5 * 10^2
等于:
sector_pos[SID] = 512 + 5 * 1024

四. 扇区配置

1. 主扇区配置表

• 主扇区配置表（MSAT：master sector allocation table）是一个SID数组，指明了所有用于存放扇区配置表（SAT：sector allocation table）的sector的SID。MSAT的大小（SID个数）就等于存放SAT的sector数，在头中指明。

• MSAT的前109个SID也存放于复合文档头(Header)中，如果一个MSAT的SID数多余109个，那么多出来的SID将存放于sector中，头中已经指明了用于存放MSAT的第一个sector的SID。在用于存放MSAT的sector中的最后一个SID指向下一个用于存放MSAT的sector，如果没有下一个则为End Of Chain SID（-2）

• 存放MSAT的sector的内容：（s_size表示sector的大小）

• 最后一个存放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）。

2. 扇区配置表

• 扇区配置表（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的大小）

• 当通过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，见6.2节）或头（内部控制流）或目录流本身获得。

五. 目录

1. 目录结构

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

• 如下图所示：

  1 2 3 4 5 6 7 8 9

  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）必须有相同数目的黑节点。

• 例：以第一章中的图为例

  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。

• 在构建红黑树的过程中，一个节点究竟作为左还是右，是通过比较其名字来判断的。一个节点比另一个小是指其名字的长度更短，如长度一样，则逐字符比较。

  规定：左节点<根节点<右节点。

2. 目录入口

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

文章原地址: https://www.cnblogs.com/AspDotNetMVC/p/3810839.html

赏

感谢大佬

微信