引言
PPT（Microsoft Office PowerPoint），是微軟公司開發的編輯演示文稿的辦公軟件。該格式相對于txt、chm等，信息量更大，結構也更加復雜，導致其對硬件配置要求較高。然而，目前嵌入式終端配置低，因此本文聚焦于滿足人們對于移動閱讀的基本需求，暫不考慮視頻、音頻和外部對象等特性支持。本解析器在開源環境下，基于Linux操作系統實現。基于嵌入式多格式解析引擎系統架構和中間格式理論，具有平臺無關性、高效性的特點。
1 系統特點
該解析引擎兼容版本多，包括Microsoft PowerPoint 972003等版本。下面介紹一下系統特點。
① 不依賴于圖形服務器。解析引擎擁有自己的專用的矢量圖形繪制器。不依賴于特定的底層圖形服務器。例如，我們的實驗系統的圖形服務器由nanoX改為Qt時，該解析引擎不需要修改。
② 高效性。對于一般的格式解析器，樣本文件越大，打開速度越慢，而該解析器可以做到文件打開速度與文件大小基本無關。
③ 平臺無關性。解析引擎并不是直接在顯示設備上繪制圖形和文字，而是把各種格式元素繪制在一段內存區域上，然后把這段內存數據映射到物理設備上。即輸入是文件，輸出是屏幕大小的位圖。
④ 配置靈活。解析引擎的模塊化設計便于移植和裁剪。所有數據類型采用宏定義，便于根據平臺配置。
⑤ 支持手寫批注。 解析器只做內容抽取和顯示，不支持編輯和保存，支持手寫批注。手寫批注不改變原文檔，而是新建xml描述文件。
⑥ 個性化交互方式。利用電子紙控制器的16通道和黑白刷，實現動畫切換效果。
2 格式分析
2.1 總體結構
Microsoft PowerPoint使用OLE2組合文檔存儲。和文件系統結構類似，它包含容器和流，并組成的樹狀結構。各種流獨立存儲，便于載入和快速保存。如表1所列，PPT文件包括以下5種流式數據。
表1 PowerPoint文件結構
PPT存儲格式采用十六進制，small endian字節序，分為若干個大數據塊和小數據塊，大小分別為512字節和64字節，第一個數據塊為初始數據塊，存儲了數據塊索引表。
2.2 圖像流結構
PPT中包含矩形、圖片框、文本框、線、橢圓等204種形式的元素，統稱為Shape。每種Shape有一個唯一的實例碼與之相應。
多媒體數據的層次結構如圖1所示。
圖1 容器層次結構
Drawing GROUP為組合圖形存儲結構，它包含了一組圖形對象。Drawing為圖形存儲結構，Shape和Solver為兩組圖形屬性元數據。Blip Store為插入的圖片對象。Property Table為缺省屬性表。Client Data為一組元數據信息，包含坐標，文本和OLE數據和用戶自定義屬性表。
屬性項采用idvalue結構，自定義屬性表的長度可變。各項屬性相對位置不變。自定義屬性表中出現的屬性將覆蓋默認屬性。
Drawing為一組描述來管理容器中的圖形對象的規則集合，包括對齊方式、標尺等。
摘要： 根據目前主流電子紙閱讀器硬件資源有限、要求功耗小、灰階顯示等特點，提出了一種PPT格式文檔解析方案。聚焦于滿足人們對于移動閱讀的基本需求，選取了文字、圖形、圖像作為基本解析對象，設計并實現了一個適合電子紙閱讀器的PPT格式引擎，并進行了多重優化以提升性能體驗，在低端的硬件配置和有限的運行時間內完成格式解析。
引言
PPT（Microsoft Office PowerPoint），是微軟公司開發的編輯演示文稿的辦公軟件。該格式相對于txt、chm等，信息量更大，結構也更加復雜，導致其對硬件配置要求較高。然而，目前嵌入式終端配置低，因此本文聚焦于滿足人們對于移動閱讀的基本需求，暫不考慮視頻、音頻和外部對象等特性支持。本解析器在開源環境下，基于Linux操作系統實現。基于嵌入式多格式解析引擎系統架構和中間格式理論，具有平臺無關性、高效性的特點。
1 系統特點
該解析引擎兼容版本多，包括Microsoft PowerPoint 972003等版本。下面介紹一下系統特點。
① 不依賴于圖形服務器。解析引擎擁有自己的專用的矢量圖形繪制器。不依賴于特定的底層圖形服務器。例如，我們的實驗系統的圖形服務器由nanoX改為Qt時，該解析引擎不需要修改。
② 高效性。對于一般的格式解析器，樣本文件越大，打開速度越慢，而該解析器可以做到文件打開速度與文件大小基本無關。
③ 平臺無關性。解析引擎并不是直接在顯示設備上繪制圖形和文字，而是把各種格式元素繪制在一段內存區域上，然后把這段內存數據映射到物理設備上。即輸入是文件，輸出是屏幕大小的位圖。
④ 配置靈活。解析引擎的模塊化設計便于移植和裁剪。所有數據類型采用宏定義，便于根據平臺配置。
⑤ 支持手寫批注。 解析器只做內容抽取和顯示，不支持編輯和保存，支持手寫批注。手寫批注不改變原文檔，而是新建xml描述文件。
⑥ 個性化交互方式。利用電子紙控制器的16通道和黑白刷，實現動畫切換效果。
2 格式分析
2.1 總體結構
Microsoft PowerPoint使用OLE2組合文檔存儲。和文件系統結構類似，它包含容器和流，并組成的樹狀結構。各種流獨立存儲，便于載入和快速保存。如表1所列，PPT文件包括以下5種流式數據。
表1 PowerPoint文件結構
PPT存儲格式采用十六進制，small endian字節序，分為若干個大數據塊和小數據塊，大小分別為512字節和64字節，第一個數據塊為初始數據塊，存儲了數據塊索引表。
2.2 圖像流結構
PPT中包含矩形、圖片框、文本框、線、橢圓等204種形式的元素，統稱為Shape。每種Shape有一個唯一的實例碼與之相應。
多媒體數據的層次結構如圖1所示。
圖1 容器層次結構
Drawing GROUP為組合圖形存儲結構，它包含了一組圖形對象。Drawing為圖形存儲結構，Shape和Solver為兩組圖形屬性元數據。Blip Store為插入的圖片對象。Property Table為缺省屬性表。Client Data為一組元數據信息，包含坐標，文本和OLE數據和用戶自定義屬性表。
屬性項采用idvalue結構，自定義屬性表的長度可變。各項屬性相對位置不變。自定義屬性表中出現的屬性將覆蓋默認屬性。
Drawing為一組描述來管理容器中的圖形對象的規則集合，包括對齊方式、標尺等。
3 軟件設計
本設計以嵌入式多格式解析引擎系統架構為基礎。解析引擎是負責對源文件進行解析，生成中間格式需要的數據的模塊。
解析引擎的內部架構如圖2所示。
圖2 解析引擎架構
3.1 語法分析器
語法分析器為輸入流數據，輸出為結構化數據供各模塊使用。PPT格式的記錄采用idvalue結構，id和value占據規定的字節數，語法分析器負責識別記錄id，并抽取value。
3.2 導航器
負責把數據從文件系統調入內存，并把I/O流轉換成結構化數據，即用DOM結構描述文件的整體架構。
該模塊具有頁面導航作用。PPT使用OLE2組合文檔存儲。容器和結點只存儲粗粒度索引信息，對于不需要立即顯示的頁，只存儲容器結點，暫時不展開，需要顯示該頁時，再從該結點向下展開，從而減少了不必要的文件讀取。這種分層裝載方法，提高了打開速度，并且對于大文檔，進入速度只和第一頁的復雜程度有關。
此外，為了更好地索引，建立了一系列的鏈表結構。如：數據塊索引表、根目錄表、圖像數據流鏈表、用戶反向鏈表、文本鏈、母板鏈表等。
文件長度、版本號、進行文件合法性等信息通過讀取初始化塊獲得。除此之外還需要初始化幾個重要的全局鏈表。
① 數據塊索引表。文件以塊為單位存儲，且不連續，數據所屬塊號和塊內偏移量可以方便地進行尋址操作。
② 構建根目錄表，包括存儲內容的起始塊號和大小，用于尋址操作。讀操作只在當前塊范圍內，當超出當前塊可讀長度時，通過查詢塊索引表找到下一塊的塊號。
③ 構建圖像數據流鏈表。
④ 構建用戶反向鏈表。為了快速保存，PPT采用增量式存儲，即每次保存時，直接生成頁面副本并追加到文檔末尾。增量式存儲的缺點是冗余量大。例如，有的文件只有幾頁，但文件大小幾MB甚至幾十MB，文件實際大小和修改次數有關。
⑤ 幻燈片文本鏈，流信息到排版元數據獨立存儲。純文本存儲在文本流中，存儲以及排版信息存儲在頁數據區。頁數據區還存儲了純文本在文本流中的位置。
⑥ 母板鏈表，母板一般作為背景，以頁為單位順次存儲。因為電子紙顯示灰度圖像，背景和正文疊加以后看不清楚，用戶閱讀時可以去除背景，而不會影響到文件本身。
增量式存儲的基本思想是：每次修改產生一個用戶信息，存儲修改的塊號，當前用戶信息反向指向上一個用戶信息，從而構成一個用戶反向鏈。遍歷用戶反向鏈可以找到最后一次修改。冗余數據可以直接丟棄。
3.3 布局管理器
負責屏幕劃分和圖層管理，布局管理器劃為不同的矩形區域，并標識該區域的類型。然后分別將解析得到的文字，圖形，圖像緩沖區映射到屏幕位圖上。
3.4 文字處理器
PPT格式的文字種類和布局相對復雜，可以分為正文和圖形內嵌文字兩種，各級標題正文的布局也有要求。文字處理器針對各種文本的排版格式多樣性進行解析和布局，完整再現原文檔的版式信息。
文字處理過程分為預排版和頁面排版兩部分，預排版負責填充字模緩沖區，抽取字符編碼和字體信息作為FreeType的輸入，用生成的單個字模位圖填充緩沖區。然后結合標尺和對其方式把映射到頁面顯示緩沖區。文字解析原理圖如圖3所示。
圖3 文字解析原理圖
3.5 圖形渲染
負責圖形繪制和組合圖形坐標空間轉換。本解析引擎不依賴于圖形服務器，擁有專用的矢量圖形繪制庫。能夠將圖形直接繪制到頁面位圖中，與物理顯示無關。
繪制直線，曲線和多邊形填充分別采用了經典的Breshman算法，三次貝塞爾曲線畫線算法，列掃描多邊形填充算法3種成熟算法。為了提高了運算效率，對于浮點數作取整運算。經驗證，在浮點數運算效率不佳的嵌入式系統上也能到達較好的渲染效果。
組合圖形（Drawing GROUP）包含了一組圖形對象，采用了Dom結構。子結點使用相對于父結點的坐標空間。因此，圖形處理能夠遞歸地進行坐標轉化，并把圖形繪制在其父結點的坐標空間內。
3.6 圖像渲染
圖像渲染器采用Cximage圖像庫把圖像數據重構，并進一步轉化成灰度圖像放入屏幕緩沖區。
文件中圖像和多媒體信息存儲在圖像流中，通過FBSE （File Blip Store Entry）描述。于是定義了結構體：
typedef struct _FBSE{
MSOBLIPTYPE imageType;
ULONG id;
ULONG size;
ULONG cRef;
ULONG offsetInDelayStream;
}FBSE;
4 優化提速
用戶總是希望系統越快越好，但是嵌入式系統受主頻較低、內存較小的限制，對于一些計算量比較大的工作，很難達到理想的效果。于是本解析引擎在應用了多頁面緩沖機制和異步并行機制的優化策略。
各渲染器異步并行地工作，第一個完成任務的渲染器立即把數據提交給屏幕顯示。電子紙整屏刷新速度為1 s，利用這個刷屏間歇，其余渲染器完成任務，再采用局部刷屏的方式把增量部分刷新到屏幕上。這樣整體速度取決于渲染速度最慢的那一個。此外，異步執行不阻塞輸入，如果這時用戶翻頁，未完成解析線程會被終止，并建立新線程來解析下一頁。例如：打開一頁圖文混排的幻燈片，打開時先顯示文字，隨后顯示出圖像，并且不會阻塞用戶輸入，假如用戶快速連續翻若干頁后停止，中間頁解析會被終止。
5 驗證
在主頻200 MHz的電子紙閱讀器上實現效果如圖4所示。
圖4 在電子紙閱讀器上解析效果圖
隨機選擇60個樣本文件，進入書籍最短時間2.82 s，最長11.92 s.如圖5所示。
圖5 在電子紙閱讀器上解析速度統計圖
解析引擎采用分層裝載方法，提高了打開書籍速度，這里選擇了3個第一頁完全相同但是大小差別較大的PPT文檔。實驗表明，雖然文檔大小差別很大，但是打開速度差異不大。如表2所列。
表2 啟動速度對比
結語
由于電子紙的特性和嵌入式設備的資源限制，本文僅僅聚焦在常用元素的解析上，如文字、圖形、圖像、表格等，而對于嵌入對象（如視頻、音頻等）沒有支持。對于未知元素的解析將成為未來的主要工作。本文模塊化的設計架構，有利于下一步進行功能擴展，另外，隨著Office開放文檔格式（OOXML）的誕生并成為國際標準，未來將開發支持OOXML的嵌入式解析器。