Excel文件格式(BIFF)

Excel的文件格式是BIFF（Binary Interchange File Format）。从Excel97 - Excel2003使用的是BIFF version 8，可是说BIFF8是目前最广泛使用的Excel版本。BIFF8基于微软的复合文档格式。Excel文档的内容存放在一个Stream里。一个新建的空白Excel文件，一般包含Root Storge，Workbook Stream，<05H>SummaryInformation Stream，<05H>DocumentSummaryInformation Stream。Workbook Stream就存储了Excel的内容。把整个Excel文件叫Workbook，Workbook里至少有一个Worksheet。Excel文件不仅存放Excel的文本内容，还存放一些格式，比如字体信息，颜色。Excel的逻辑结构可以用下图表示：

Workbook globals里就记录了整个Workbook公用的东西，比如格式，字符串常量，文档保护等。worksheets，workbook globals都是存储在Workbook Stream里，可以把它们看做是substream。各个substream按一定顺序出现在Workbook Stream里，如下图所示：

图中所示，Globals Substream是必须的，而且至少保护一个Sheet Substream。那么这些Substream是如何区分开的，如何知道一个Substream从文件的哪个位置开始，哪里结束呢？这得从BIFF8描述信息所采用的格式来说。这里说的"信息"，包含很多，比如格式信息，位置信息，文本信息，图片信息，宏代码信息，等等。这么多信息要记录，BIFF8是采用Record的方式来记录的。一个Record描述一个信息。因此有很多种Record。因此Record Type肯定是Record数据结构的组成部分。Record是不定长的，种类非常多，各个种类的内容格式千差万别。但是基本遵循如下的结构：

结构包含两部分，Record Header和Record Data。Record Header部分的前2字节是Record Type，然后是2字节描述Record Data的长度。文档给出了几乎所有的Record Type，针对每种Record，描述了Record Data里各字节的含义。Substream的开始和结束，就是采用BOF和EOF这两个Record Type。也就是说在Workbook Stream是Record序列，一个Record接着一个Record，有些BOF的record表示接下来要描述一个Substream了。因此处理程序可以一个Record一个Record的读取，先检查读入的Record的Type，如果不认识，那么就不处理Record data部分，如果认识就解析Record data部分的含义。Excel的版本是不断升级的，补丁是不断更新的，新的版本，新的build就可能有新的Record Type。因此旧版本的Excel打开高版本的xls文件，有些Record就无法识别，但是不影响基本数据的读取。FastExcel就是根据这个原理，只处理一些和文本内容相关的必需的Record Type，像格式之类的Record就不处理了，因此就Fast了。
当一个Cell的内容为字符串常量时，BIFF8一般把这个字符串常量用SST这种Record记录在Global Substream，然后在Sheet Substream里使用LabelSST这种Record引用这个字符串。LabelSST这种Record的Record Data部分就包含了行号，列号，字符串索引号（index）等信息。查看文档，可知LabelSST类型的Record Header的Identifier是00FD(hex)，size是10，Record data结构如下图所示：

FastExcel的项目主页也说了它们只实现了如下的Parser来处理一些Record，仅仅是针对文本内容，BIFF8的Record类型可是几百个。这里的BOFParser就是处理BOF类型的Record，LabelSSTParser处理LabelSST类型的Record。
* BOFParser
* EOFParser
* BoundSheetParser
* SSTParser
* IndexParser
* DimensionParser
* RowParser
* LabelSSTParser
* RKParser
* MulRKParser
* LabelParser
* BoolerrParser
* XFParser
* FormatParser
* DateModeParser
* StyleParser
* MulBlankParser
* NumberParser
* RStringParser
BIFF8里多字节数据，比如4字节整数，2字节整数，Unicode都是采用Little-Endian的存储方式。

微软复合文档格式 (Compound Document)

今天看到一个FastExcel的开源项目，它能够使用纯Java代码读取Excel文件的文本内容以及写入内容保存为Excel文件。这项目的作者应该是一个中国人，因为项目源代码中包含的JUnit测试代码里居然有中文数据。把项目的源代码导入到Eclipse编译，运行了附带的测试用例。源代码里的package开头是edu.npu。baidu一下，npu好像是西北工业大学。作者在项目的简介里介绍了代码的工作原理是依照Excel的文件格式，直接进行读取。而Excel的文件格式是基于复合文档(Compound Document)的。项目主页上有链接给出复合文档格式和Excel文件格式，都是OpenOffice社区整理的。
复合文档简单的说就是在一个文件里可以内嵌其他各种文档，这些内嵌的文档还具有目录结构，可以说复合文档格式就是在一个文件里面实现一个文件系统。从逻辑上说复合文档包含Storage和Stream。Storge相当于我们熟知的操作系统文件系统里的目录，Stream相当于文件。下图就是复合文档的逻辑示意图。和操作系统的文件系统类似，同一个Storge下的Stream不可以重名，不同Storage下的则可以。

其实这个图的内容，很久之前我就了解了，而且很好理解。当初看MFC书籍讲复合文档的时候就在这个层次上。自己也没深究过要实现这样的逻辑结构，物理上该如何存储。今天特地阅读了这个文档格式，25页，不是很长，边阅读边查看一个Excel文件的物理存储结构，这样更好理解。
物理结构图：

开始是一个文件头（Header），固定长度512字节。然后是一个接一个的扇区（Sector），大小是可变的，一般是512字节。这里的Sector可以类比为磁盘上的扇区，反正就是一块文件空间。一个复合文档，除了文件头就是扇区。因此复合文档的内容数据主要是存放在扇区里的。此外有些扇区得用来存储一些元数据，描述扇区和扇区之间的关系，哪些扇区是用来干嘛的，那几个扇区组成一个Stream。每个扇区有一个标识符，也就是编号，从0开始，依次递增。扇区的编号用有符号的4字节整数来表示，这样在内部就可以引用了。扇区号可以是负数，几个负扇区号的特殊含义是:

就像磁盘文件系统，一个文件有多个块组成，在复合文档里，一个Stream也是由多个Sector组成。那么多个Sector的顺序是怎么样的？一个Stream到底有几个Sector组成呢？这是通过Sector Allocation Table（SAT）来实现的。SAT顾名思义就是跟踪Sector的分配情况。SAT也得需要空间来存储啊！当然也是存储在Sector里的。可以说SAT也是一种特殊的Stream，它描述一个Stream拥有哪些Sector。那么谁描述它自己拥有哪些Sector呢？是MSAT，Master Sector Allocation Table。MSAT描述了哪些Sector是被SAT占用的。那谁描述MSAT存放在哪些Sector？好像无休止了！MSAT是存放在Header里的。这下摆脱溯源的烦恼了。但是Header大小是固定512字节的，因此能存的信息是有限制的。如果SAT占用的Sector很多很多，Header里都描述不下，怎么办？还是有办法的，扩展！当Header里的空间不够用时，就用Sector，在Header里有字段记录哪个Sector是MSAT扩展空间的第一个扇区，在MSAT专用的扇区里的最后4字节给出下一个MSAT专用的Sector，这样一个链表就现成了。因此一个MSAT扇区最多可以记录(512-4)/4=127个AST扇区。

通过MSAT就可以找出所有被SAT占用的Sector。这些SAT的Sector就描述了哪个几个Sector是属于一个Stream的以及Sector之间的顺序。这似乎又需要一个链表。对的。这次的链表结构是这样的：



把SAT看做一个数组，数组的元素就是扇区编号，扇区编号用4个字节来存储。比如SAT[i] = j，表示SAT数组的第i个元素是扇区编号j。如果把数组索引就当做扇区编号，SAT[i] = j，SAT[j] = k ... SAT[x] = -2，那么就有一串扇区编号了，i -> j -> k ...-> -2，扇区号-2表示串的结尾。这样，Stream就可以用这么一串扇区序列来描述的，关键是能有一个元数据描述这个Stream，并记录这个Stream的起始扇区号。知道了起始扇区号，就可以通过SAT找到所有其他Sector了。可见SAT也是一个链表结构。好像学数据结构的时候学过这种结构，具体叫啥忘记了。
那怎么存储Stream元数据呢？毫无疑问，是存放在Sector里。SAT就是存储了一些扇号串，看不出哪一串是用来描述Stream的元数据的。于是复合文档就有另一个概念了，目录（Directory）。Directory包含一个描述Stream和Storge的元数据的数据结构。如下图所示，目录里面有目录项，目录项也有编号，从0开始。
每个目录项就描述该项是Stream还是Storge，或者其他。如果是Stream，那么就记录起始扇区号是多少，如果是Storge，包含记录它有哪些Storge和Stream。一个Storge下可能有很多个Storge和Stream。复合文档是把这些子Stream和Storge组成一棵红黑树。这样Storge就可以只记录这颗红黑树的根节点就达到记录所有子Storge和Stream的目的。当然每个目录项得有字段里维护这么一颗红黑树。显然这种方式下，一个Stream或Storge只能在一棵红黑树里。为啥使用红黑树，有什么优点？慢慢思考中！
此外，复合文档还有其他一些概念，比如Short-Stream。Short-Stream一般存储在Root Storge这个目录项里。